Комментарии 26
Сравниваем встроенную сортировку (O(n2)), сортировку слиянием (merge sort) (O(n log n)) с поразрядной сортировкой (radix sort) и побитовыми операциями.
1) Встроенная сортировка имеет n*log(n) сложность.
2) Сравниваете generic реализацию сортировки из стандартной библиотеки со своими реализациями в которых зашит int.
3) Radix сорт в отличие от например q-sort имеет еще и накладные расходы по памяти.
Вообщем сравнение некорректное как по мне.
Ориентация была на quick sort
В самом начале было обозначено, что работаем с int значениями. Хотелось посмотреть именно для каких-то равных условий.
Согласна, имеет. Но не настолько большие как в случае с merge sort.
Задача не стояла сравнить именно сортировки. Оценить - да, для каких-то равных условий. И какое место во всем этом занимает radix sort
1 В том числе о нем и речь, откуда n^2?
2 Так в том и дело что вы написали алгоритм для интов а в стандартной библиотеке generic алгоритм, откуда тут равные условия
Быстрая сортировка всегда была в худшем случае n^2, а не той сложности, которую Вы указали
Мы работаем с побитовыми операциями, а это не float, объекты или что-то другое. Это int значения. В рамках данного контекста выжимаем и смотрим на окружение - можно ли улучшить. Сравнивать все со всеми (если говорить только о сортировке) - целесообразно в отдельной статье.
1 А поиск в хеш таблице с бакетами О(n) в худшем случае, только думается на собеседовании в озон ожидают другого ответа на вопрос о сложности поиска в хэш таблице ;)
Возвращаясь к квиксорту- зависит от выбора опорного элемента, применяя простые техники вероятность получить квадрат очень низкая. Так что обычно говорят об ожидаемом времени работы - nlog n. Загляните в сорцы стандартной сортировки, там должно быть что то про сложность.
2 Вы видимо не понимаете в чем претензия. Дело в том что в текущем go производительность обобщенного алгоритма будет ниже производительности того же алгоритма написанного с конкретным типом данных. Это происходит из-за того что go не выведет тип на этапе компиляции - соответсвенно будут накладные расходы в рантайме.
Мы говорим на разных языках. В данном контексте меня не интересует, что под капотом. Интересует результат. Выбиралась та кастомная реализация, которая ориентирована на целочисленную сортировку. Согласна, что можно реализовать не одну, а несколько. Только не об этом немного речь.
Ну так почему в оппоненты своей реализации вы берёте generic реализацию?
Напишите квиксорт для слайса интов- тогда будет честное сравнение (и думается radix не выйдет из него победителем).
Так как реализована еще сортировка слиянием. И в среднем она лучше по времени, чем быстрая. Закономерность прослеживается, что смысла реализовывать ее нет. Тем более в данном контексте. Про radix sort Вам так хочет казаться? Точно также можете вначале изучить вопрос. Быстрая сортировка может быть быстрее только при небольших числах.
Извините но ваши выводы о сортировках - это без комментариев, информация вроде в открытом доступе есть, уж по квиксорт vs mergesort точно.
Спор по производительности тоже банальный, вот бенчмарк (из вашей статьи), можете запустить и убедиться:
Quick sort - быстрая. Никто не спорит, но не стабильная. Почему этот вопрос для Вас так важен в теме, которая совершенно не об этом. Я вот никак понять не могу.
Давайте не переводить разговор в русло: "почему комментатор комментирует". Because i can.
По поводу темы - я не считаю что не об этом. Вы обозначили преимущества поразрядной сортировки в общем случае (да в частных случаях она может быть хороша - но в статье я не вижу об этом), я с этим не согласен и привожу свои аргументы.
*при небольших объемах - имелось ввиду. Про radix sort выше
Ну наконец-то!
Большинству современных "сеньоров" приходится вместе с приходящей из бакенда битовой маской читать курс битовых операций, чтобы они правильно реализовали бакендный замысел. Очень люблю использовать битовые поля и маски при манипулировании компактными наборами признаков, например, таких как аналоги связей многие-ко-многим.
Так а вам это реально надо — вы устраняете критичный ботлнек по трафику или производительности? Или ключевые слова вашего тезиса — "очень люблю использовать", а всё остальное вытекает из них?
Я это спрашиваю только потому, что в свое время (в 2011 году, если всё правильно помню) — видел таких любителей битовых масок для классификаторов. Рядом с их красивыми битовыми масками в xml с enterprise-grade тегами (полное имя java-классов из сериализатора) лежали так же пространнейшие описания категорий (тех, для которых классификаторы), местами повторяемые. Итого в xml на пару мегабайт за запрос пара мест была длиной не условно 30 знаков (0000101001001000101 в виде строки), а 3-5.
Но когда я этих любителей битовых масок спросил про то, почему бы им не переписать сериализатор хотя бы на куда более компактный json, или там, не дублировать очень длинные описания категорий в выдаче — мне в ответ почему-то сделали круглые глаза: ты чё, это ж интеграционные зависимости поедут! Обратную совместимость делать! Архитектуру переутверждать!!! Тупой фронтэндер ничего не понимает, а еще и в битовые маски не очень может!
Типичные применения - список ролей юзера в системе, или права доступа к экземпляру объекта по ролям - если вариантов заведомо меньше 32(64), то добавление поля-битового вектора int(long) - превосходная альтернатива node list в XML, array в JSON или второго рекордсета при табличной выдаче из БД. Проверка на наличие признака при этом - простейшая логическая операция со скаляром по сравнению с поиском в объекте-хэштаблице. Если таких операций много и/или делаются они часто - тратить на них лишнюю память и процессор совершенно нет необходимости
Если таких операций много и/или делаются они часто
Ну вот вы не в теории, а на практике можете сказать, где не на бэкэнде надо много (очень много) раз проверять наличие роли для объекта?
Конечно. Например фильтрация строк данных по маске прав доступа.
PS помнится, вектор пермиссий в файловой системе RSX-11 занимал одно 16-битное слово с битами RWED в каждом ниббле для системы, владельца, группы и гостей. Сейчас бы нагородили вложенных объектов весом в половину адресного пространства тех времён ;)
Я только не совсем понимаю, к чему Вы аппелируете. К тому, что скаляры не дают экономии? К тому, что в современном мире экономить не нужно/лень разбираться? К тому, что исчезли задачи, в решении которых можно применить экономию? Или к тому, что я их придумал искусственно?
С очень специфическими рамками:
1) Эта фильтрация не убрана полностью на бэк
2) Есть очень (очень) много объектов, настолько много, что скорее всего одна их загрузка занимает существенное время
3) Мы работаем на каком-то покалеченном устройстве (смарт-тв, не иначе), где заведомо нет памяти и хреновый процессор.
Если не выполняются №2/№3, то фильтрацию можно либо сделать один раз, просто раскидав объекты по группам заранее (причем в фоновом режиме), либо же просто фильтровать хешмапами и никто не умрёт. Для ощутимой невооруженным взглядом выгоды надо иметь именно довольно слабый процессор и очень большие объемы данных.
Я только не совсем понимаю, к чему Вы аппелируете.
К тому, что ваш начальный комментарий попахивает повальным обобщением, в то время как в реальности ситуации, когда на фронте нужно как следует поэкономить на памяти и тактах через битовые маски — они безусловно есть, а на проектах определенного вида (карты, видео, итп) — очень сильно есть, но в среднем по фронту они крайне редки.
В среднем, на фронте экономят не на битовых масках, а на гораздо более прозаичных вещах.
Так а почему речь идёт только о фронте? Бакенду тоже проще выдать int из плоской таблицы, чем выборку ассоциации из many-to-many через лишние два джойна и один резалтсет. Притом что, «вас много, а я тут одна» - то есть экономия ресурсов на баке более важна, так как каждый юзер приносит с собой на фронт кристалл ЦПУ и несколько гигов памяти, но на бак почему-то заносить забывает ;)
То же относится и к фильтрации строк - неважно по сути, где она делается - проверка битовой маски быстрее проверки ассоциации
Бакенду тоже проще выдать int из плоской таблицы, чем выборку ассоциации из many-to-many через лишние два джойна и один резалтсет.
Конечно, но тут мы уходим в глубокий оффтопик на совсем отвлеченные темы (синхронизация данных, их версионность, etc). Тут оно тоже далеко не так просто, чтоб считать всех, делающих два джоина и один резалсет — не очень умными.
Какая синхронизация и версионность? Причем здесь вообще ум тех, кто делает через ассоциации в сравнении с теми, кто использует битмаски? Манипуляции с битами - это не rocket science абсюлютно - и по большому счету. не сложнее манипуляции с хэш-таблицами или коллекциями. Просто нужно привыкнуть использовать этот незаслуженно забытый аппарат там, где он может дать преимущество, или там, где инженер сочтет это преимущество значимым для разрабатываемой системы.
В первом комментарии я писал лишь о том, что работа с битами сейчас - настолько редкий случай среди [не-эмбед] разработчиков, что когда они встречают битовую карту - не знают, что с ней делать - примерно так, как большинство водителей, годами успешно ездящие в мегаполисе, теряются, увидя на перекрестке регулировщика - так как видели его последний раз посредине перекрестка разве что в экзаменационных билетах.
При этом, очевидно. существуют случаи когда битовые поля чрезвычайно эффективны даже в классических не-эмбед применениях на всех уровнях имплементационного стека. Заметьте, я не говорил, что по-другому делать - это sucks, я просто сказал, что сам, лично, люблю использовать битовые поля там, где это возможно делать (может быть от того, что когда-то программировал системы с 64К адресного пространства). Вот и все.
Говоря о битовом представлении данных, нельзя не упомянуть перцептивные хэши, расстояние Хэмминга и шикарную статью о подсчёте единичных битов. Так что тема раскрыта не полностью :)
Не совсем понял про обмен значений двух переменных
a = 7; b = 3;
a = a ^ b ^ a; // a = 3, b = 3 эквивалентно a = b;
b = ?
Применение двоичной логики в недвоичных операциях: оптимизируем производительность и ресурсы