Научпоп, с цветными картинками: https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

В нашей статье, опубликованной 7 июня в журнале Nature, мы представляем AlphaDev, систему искусственного интеллекта (ИИ), которая использует обучение с подкреплением для открытия усовершенствованных алгоритмов информатики, превосходящих те, которые ученые и инженеры оттачивали десятилетиями.

Благодаря открытому исходному коду наших новых алгоритмов сортировки в основной библиотеке C++ миллионы разработчиков и компаний по всему миру теперь используют его в приложениях ИИ в различных отраслях, от облачных вычислений и онлайн-покупок до управления цепочками поставок. Это первое изменение в этой части библиотеки сортировки более чем за десятилетие, и впервые в эту библиотеку был добавлен алгоритм, разработанный с помощью обучения с подкреплением. Мы рассматриваем это как важный шаг к использованию ИИ для оптимизации мирового кода, по одному алгоритму за раз.

AlphaDev основан на AlphaZero , нашей модели обучения с подкреплением, которая побеждала чемпионов мира в таких играх, как го, шахматы и сёги. С помощью AlphaDev мы показываем, как эта модель может быть преобразована из игр в научные задачи и из симуляций в приложения реального мира.

Чтобы обучить AlphaDev открывать новые алгоритмы, мы превратили сортировку в «игру по сборке» для одного игрока. На каждом шагу AlphaDev наблюдает за сгенерированным алгоритмом и информацией, содержащейся в центральном процессоре (ЦП). Затем он выполняет ход, выбирая инструкцию для добавления к алгоритму. Игра на ассемблере невероятно сложна, потому что AlphaDev приходится эффективно перебирать огромное количество возможных комбинаций инструкций, чтобы найти алгоритм, способный сортировать и работающий быстрее, чем текущий лучший из них. Количество возможных комбинаций инструкций аналогично количеству частиц во вселенной или количеству возможных комбинаций ходов в играх в шахматы (10 120 игр) и го (10 700 игр). И одно неверное движение может свести на нет весь алгоритм.

AlphaDev обнаружила новые алгоритмы сортировки, которые привели к улучшениям в библиотеке сортировки LLVM libc++, которая стала на 70 % быстрее для более коротких последовательностей и примерно на 1,7 % быстрее для последовательностей, превышающих 250 000 элементов. Мы сосредоточились на улучшении алгоритмов сортировки более коротких последовательностей из трех-пяти элементов. Эти алгоритмы являются одними из наиболее широко используемых, потому что они часто вызываются много раз как часть более крупных функций сортировки. Улучшение этих алгоритмов может привести к общему ускорению сортировки любого количества элементов.

Суровый не научпоп: https://www.nature.com/articles/s41586-023-06004-9

Коммит: https://reviews.llvm.org/D118029

Igor van den Hoven много экспериментирует с алгоритмами сортировки.

Например, blitsort:

                 ┌───────────────────────┐┌───────────────────────┐
                 │comparisons            ││swap memory            │
┌───────────────┐├───────┬───────┬───────┤├───────┬───────┬───────┤┌──────┐┌─────────┐┌─────────┐
│name           ││min    │avg    │max    ││min    │avg    │max    ││stable││partition││adaptive │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│blitsort       ││n      │n log n│n log n││1      │1      │1      ││yes   ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│crumsort       ││n      │n log n│n log n││1      │1      │1      ││no    ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│fluxsort       ││n      │n log n│n log n││1      │n      │n      ││yes   ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│mergesort      ││n log n│n log n│n log n││n      │n      │n      ││yes   ││no       ││no       │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│quadsort       ││n      │n log n│n log n││1      │n      │n      ││yes   ││no       ││yes      │
├───────────────┤├───────┼───────┼───────┤├───────┼───────┼───────┤├──────┤├─────────┤├─────────┤
│quicksort      ││n      │n log n│n²     ││1      │1      │1      ││no    ││yes      ││no       │
└───────────────┘└───────┴───────┴───────┘└───────┴───────┴───────┘└──────┘└─────────┘└─────────┘

Всем быстрой стабильности!

поиск, параметр только темы, но выдает темы, в названии которых нет искомого слова.

IMG

В общем, в чём идея: по работе нужно иметь кучу вкладок (20+ на задачу иногда, задачи могут висеть неделями), и если эта вся котовасия открыта сразу - найти нужное почти нереально. Реквестируется способ или идея, как разделить вкладки по задачам и не листать по 500 штук, а выбирать, собственно, из списка задачу, а уж после получать список нужных вкладок. Идею с кучей экземпляров браузера не предлагать, слишком топорно.

Существует ли программа, которой можно задать папку, откуда нужно выдавать изображения, и чтобы я выбирал, в какую папку какое изображение класть? Например есть несколько целевых папок, каждой папке соответствует своя клавиша, и при нажатии на одну из них, изображение попадает в нужную папку.

Есть что-то на подобии?

Всем привет.

Пытаюсь разобраться с Zenbot. Поставил его на убунту, все отлично работает, делает вытяжку исторических данных по указанным мною параметрам. Вот к примеру командой делаю вытяжку за 30 дней (./zenbot.sh sim kraken.XXBT-ZEUR --days 30) и в конце он создает файл html результат.

И в консоли вот вытяжку выводит, которая мне и нужна (вот пример скопирован из консоли в ворд без имени.docx). Но с консоли оно копирует тупо одной строкой или как-то криво, хотелось бы как то разделить все это по столбцам как в консоли, что-бы удобно было фильтровать по дате например и остальным критериям.

Лазил в коде и наткнулся, что в файле js (https://github.com/DeviaVir/zenbot/blob/unstable/commands/sim.js) вроде идёт речь о создании файла результате html, и как бы csv файл должен быть, ну как его получить не пойму? Кто имел опыт с ботом или как хотя-бы из консоли правильно скопировать данные?

Заранее благодарен.

Прочитал статью на русском, из которой сделал вывод, что < и > сравнивают длину строки по количеству символов. Но потом попробовал разные примеры, и оказалось что тут другое. В английском руководстве такое определение.

string1 < string2

    True if string1 sorts before string2 lexicographically.
string1 > string2

    True if string1 sorts after string2 lexicographically.

Т.е. возвращает тру, если 1я строка сортируется перед/после 2й строки лексикографически- дословный перевод.

Что-то я не до конца понял «сортируется перед/после». Почему строка «ссссс» считается длиннее «ccccb», но короче, чем «cccce». Ну интуитивно логику я понял (алфавит по порядку), но ведь строки то по сути равны. В обоих по 5 символов.

Вот мы числа сравниваем: 10 > 2 - это очевидно, даже сомнений не возникает. А тут мы сравнили 2 строки по 5 символов, и выясняется, что одна из них почему-то больше, по правилам какого-то алфавита... Допустим так, я не против. Но кому вообще (и зачем) придет в голову мысль выяснять таким способом «длину строки». В чем тут практический смысл? Где применяется?

Как отсортировать по названию каналов из скрипта?

#EXTINF:-1 catchup group-title="Познавательные" tvg-id="738589577doktor",Доктор
http://192.168.1.166:9090/InternationalID=1686
#EXTINF:-1 catchup group-title="Познавательные" tvg-id="738589577texno24",Техно 24
http://192.168.1.166:9090/InternationalID=1687
#EXTINF:-1 catchup group-title="Развлекательные" tvg-id="738589577360news",360°
http://192.168.1.166:9090/InternationalID=1688
#EXTINF:-1 catchup group-title="HD каналы" tvg-id="738589577360news",360° HD
http://192.168.1.166:9090/InternationalID=1689
#EXTINF:-1 catchup group-title="Общественные" tvg-id="7385895778kanalru",8 канал (Россия)
http://192.168.1.166:9090/InternationalID=1690
#EXTINF:-1 catchup group-title="Музыка" tvg-id="738589577tntmusic",ТНТ MUSIC
http://192.168.1.166:9090/InternationalID=1691
#EXTINF:-1 catchup group-title="Фильмы" tvg-id="738589577amedia1",A1

привет всем. Накопилась туева хуча файлов на террабайтном диске, без понятия как вообще их каталогизировать и отсортировать. Как-то давно читал о проге которая при перетаскивании на ее окно файлов раскидывает их по директориям согласно типам файлов. Кто знает что это за программа?

Доброго времени суток, до меня очень туго доходит работа с переменными в линукс, да и вообще я плохо в этом понимаю. Но для меня встала задача отсортировать файл, я конечно сначала много гуглил и пытался, но результата это не дало. Задача состоит вот в чем. Есть .txt такого вида

WIN-QTHENOOT\Administrador;WIN-QTHENOOT\suporte; WIN-JQMPVQMA\administrador;WIN-JQMPVQMA\informix; WIN-MSHICLTI\Administrador;WIN-MSHICLTI\Everson Vian do amaral;WIN-MSHICLTI\informix; WIN-NEMEALTN\Administrador;WIN-NEMEALTN\informix; SRVDIBRM\Administrador;SRVDIBRM\done;SRVDIBRM\Alessandro;SRVDIBRM\Leticia;

я хочу его отсортировать, сохранить то что находится между \; остальное удалить. Вот что должно получится

Administrador; suporte; administrador; informix; Administrador; Everson Vian do amaral; informix; Administrador; informix; Administrador; done; Alessandro; Leticia;

Каждый пользователь должен быть с новой строке

подскажите алгоритм «перемешки с приоритетом»

хочу примерно следующее

const result = shuffleWithPriority([{el: 1, priority: 0.1}, {el: 2, priority: 10}, {el: 3, priority: 5}])

где в результате будет скорее всего 2,3,1, иногда 3,2,1, и совсем редко 1,2,3 либо 1,3,2

В идеале готовый код на npm, либо код на js. Но и просто описание подойдет.

По поводу эффективности, не критично, но желательно не больше чем O(n^2)

UPD решение

генерируем [псевдо]случайное число от 1 до <максимальный приоритет>
умножаем приоритет на получившееся число
сортируем в порядке получившихся приоритетов

Добрый день!

Возникла необходимость архивировать файлы tar'ом. Архивировал так:

tar -cvzf 2018_log.tar.gz /opt/name/name2/logs/*2018*

У меня архивировались логи в указанной директории, в названии которых было «2018».

С этим было все ок.

Сейчас же надо архивировать файлы, название которых не содержит даты создания, возник вопрос: можно ли как то указать, что бы архивировались файлы созданные в определенный год? В гугле, к сожалению, толкового ничего не смог найти (возможно плохо искал).

Нашел только вариант с сортировкой через find, и после этого запустить архивирование, но не знаю насколько это будет корректно.

Спасибо!

Вышло новое издание (март 2019ого) книги Седжвика «Алгоритмы на C++», немного побуду слоупоком, но сам только с неделю назад увидел. Можно заказать на OZONe за 2800р, что я, собственно и сделал. На Лабиринте стоит сумасшедших 5100р. Так что если кто хочет и интересуется - советую взять, через недели две отпишусь о качестве перевода (надеюсь, что будет время нормально ознакомиться).

Куда сегодня лучше идти в Айти? (комментарий)

Это же дно! Считают ли остальные господа модераторы достойным держать такого человека в своих рядах? И допускать его к модерированию технического ресурса, на котором затрагиваются сложные вопросы из теории алгоритмов, языков программирования и компиляторов? Или некоторые другие модераторы тоже не слышали про сортировку пузырьком? Признавайтесь!

Перемещено Shaman007 из linux-org-ru

В конфиге установлен параметр

force_sort_criteria=-dc:date

Добрый вечер, прошу помощи. Никак не получается выполнить задание: Вывести два первых элемента рекурсивного списка имен и атрибутов файлов в директории lab0, заканчивающихся на символ 'd', список отсортировать по убыванию даты доступа к файлу.

Есть выпуклая оболочка, в коде - это список пар x и y. Мне необходимо было вписать внутрь максимальный по площади треугольник. Для этого надо отсортировать точки выпуклой кривой по часовой стрелке. Каким образом я могу это сделать?

Необходимо отсортировать фотограции по цвету(гамме) чтобы изображения гармонировали друг с другом.
Под windows есть ImageSorter, а под линукс есть что нибудь?

Единственный выход это:

for file in *.jpg
do
  filename=`convert $file -scale 1x1\! txt:- | tail -n 1 | awk -F\( '{print $2}'|cut -d\) -f1|awk -F\, '{print $1$2$3}'`

  extension=".jpg"
  while [ -f "$filename$extension" ]
  do
    random=`echo $RANDOM % 10 + 1 | bc`
    filename=$filename$random
  done

  mv $file $filename$extension
done

Есть массив @array состоящий из хэшей %hash, в каждом хэше есть поле %hash{id}, как отсортировать хэши в массиве по этому полю?

#!/usr/bin/perl
use strict;
use warnings;

my $a=2;
my $b=5;
my $c=1;
my %hash;
my @array;

%hash=('id'=>$a);
push (@array,{%hash});

%hash=('id'=>$b);
push (@array,{%hash});

%hash=('id'=>$c);
push (@array,{%hash});
          
foreach (@array) {
    print @$_{id}, "\n";
}

exit 0

на выходе имеем.

2 5 1

а надо получить.

1 2 5

Вопрос по сабжу. Беру пример, положим, отсюда — https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#C

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
 
int main(int c, char **v)
{
        while (--c > 1 && !fork());
        sleep(c = atoi(v[c]));
        printf("%d\n", c);
        wait(0);
        return 0;
}

Вопрос, что является сортирующим механизмом в данном случае, планировщик ОС?

Ведь исходный ввод намеренно может быть случайно упорядочен.

Милости прошу в тред.