Re[3]: Вот так вот хипстеры сейчас на го сортируют
От: Hobbes Россия  
Дата: 13.05.20 14:37
Оценка: +2 :)
Здравствуйте, Мирный герцог, Вы писали:

МГ>как бы ты например отсортировал 2^32 32-битных целых?


Сортировка подсчётом. Надо всего-то 16 Гб памяти
Re[3]: Вот так вот хипстеры сейчас на го сортируют
От: vsb Казахстан  
Дата: 13.05.20 15:48
Оценка: +2
Здравствуйте, Мирный герцог, Вы писали:

vsb>>А как надо? По-моему очень изящное решение. Мне нравится такой подход.


МГ>при ограничении по памяти — внешняя сортировка


Ты точно понимаешь, что такое mmap? Ты можешь сделать mmap на файл любого размера (на 64-битной ОС) имея память любого размера. И ОС будет загружать/выгружать всё сама. От тебя требуется только обеспечить правильный паттерн доступа (например сортировка пузырьком это плохой вариант).
Отредактировано 13.05.2020 15:49 vsb . Предыдущая версия .
Re[4]: Вот так вот хипстеры сейчас на го сортируют
От: Мирный герцог Ниоткуда  
Дата: 13.05.20 16:02
Оценка: +1
Здравствуйте, vsb, Вы писали:

vsb>Ты точно понимаешь, что такое mmap? Ты можешь сделать mmap на файл любого размера (на 64-битной ОС) имея память любого размера. И ОС будет загружать/выгружать всё сама. От тебя требуется только обеспечить правильный паттерн доступа (например сортировка пузырьком это плохой вариант).


вот как раз таки потому что я точно понимаю что такое mmap, я понимаю что сортировка файла, отмапленного в память это клиника. Подумай на досуге сколько io операций потребуется если ты отмаппил файл и отсортировал vs скопировал в память, отсортировал и записал обратно в файл.
нормально делай — нормально будет
Re[5]: Вот так вот хипстеры сейчас на го сортируют
От: CreatorCray  
Дата: 13.05.20 16:32
Оценка:
Здравствуйте, karbofos42, Вы писали:

K>Я код не смотрел, но по описанию он вроде весь файл в память загрузил, а для этого MMF никакого профита не даёт.

Профит в том, что не надо заморачиваться с кодом для подгрузки и выгрузки — работает автоматически.
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Re[3]: Вот так вот хипстеры сейчас на го сортируют
От: Codealot Земля  
Дата: 13.05.20 16:37
Оценка:
Здравствуйте, Hobbes, Вы писали:

H>3 слова: внешняя сортировка слиянием.


Эффективность у него так себе.

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


То есть, комбинация радикс сорта и любого другого алгоритма.
Ад пуст, все бесы здесь.
Отредактировано 13.05.2020 16:47 Codealot . Предыдущая версия .
Re[3]: Вот так вот хипстеры сейчас на го сортируют
От: Codealot Земля  
Дата: 13.05.20 16:40
Оценка: +1
Здравствуйте, Мирный герцог, Вы писали:

МГ>yandex finished?


А у тебя, похоже, вообще ничего не finished?

МГ>как бы ты например отсортировал 2^32 32-битных целых?


Поразрядно, вестимо. По 16 бит за проход, например.
Ад пуст, все бесы здесь.
Отредактировано 13.05.2020 16:42 Codealot . Предыдущая версия .
Re[4]: Вот так вот хипстеры сейчас на го сортируют
От: Мирный герцог Ниоткуда  
Дата: 13.05.20 16:47
Оценка: -1
Здравствуйте, Codealot, Вы писали:

C>Поразрядно, вестимо. По 16 бит за проход, например.

учитывая то, что это будет на порядок медленнее сортировки подсчётом, а также что ты плюсанул vsb с его mmap твой уровень точно яндекс, не больше)
нормально делай — нормально будет
Re[5]: Вот так вот хипстеры сейчас на го сортируют
От: Codealot Земля  
Дата: 13.05.20 16:52
Оценка: +1
Здравствуйте, Мирный герцог, Вы писали:

МГ>учитывая то, что это будет на порядок медленнее сортировки подсчётом


Которая работает только в том случае, если можно выделить достаточно оперативки на подсчет — о чем ты не уточнял. Радикс сорт универсален и его можно втиснуть в любые ограничения по памяти.

МГ>а также что ты плюсанул vsb с его mmap твой уровень точно яндекс, не больше)


Ты так и не рассказал, чем так ужасен mmap.
Ад пуст, все бесы здесь.
Re[4]: Вот так вот хипстеры сейчас на го сортируют
От: andrey.desman  
Дата: 13.05.20 17:09
Оценка: 10 (1) +2
Здравствуйте, vsb, Вы писали:

МГ>>при ограничении по памяти — внешняя сортировка

vsb>Ты точно понимаешь, что такое mmap? Ты можешь сделать mmap на файл любого размера (на 64-битной ОС) имея память любого размера. И ОС будет загружать/выгружать всё сама. От тебя требуется только обеспечить правильный паттерн доступа (например сортировка пузырьком это плохой вариант).

Он там не сортирует по месту, мапит большой текстовый файл, потом идет по этому маппингу и разбивает этот текстовый файл на строки в свою структуру в куче. Вот и весь ммап. Толку ноль от него, но и вреда столько же.
Re[6]: Вот так вот хипстеры сейчас на го сортируют
От: karbofos42 Россия  
Дата: 13.05.20 17:38
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, karbofos42, Вы писали:


K>>Я код не смотрел, но по описанию он вроде весь файл в память загрузил, а для этого MMF никакого профита не даёт.

CC>Профит в том, что не надо заморачиваться с кодом для подгрузки и выгрузки — работает автоматически.

Подозреваю, что в варианте, когда последовательно считывается весь файл, разницы не будет ни по удобству ни по производительности.
Что fread какой-нибудь вызывай, что через mmap читай. Плюс-минус одно и то же должно быть по идее.
Re[6]: Вот так вот хипстеры сейчас на го сортируют
От: Мирный герцог Ниоткуда  
Дата: 13.05.20 20:09
Оценка: :)
Здравствуйте, Codealot, Вы писали:

C>Которая работает только в том случае, если можно выделить достаточно оперативки на подсчет — о чем ты не уточнял. Радикс сорт универсален и его можно втиснуть в любые ограничения по памяти.


я не понимаю зачем ты пишешь эти слова, причины для использования radix sort всегда можно найти, иначе его никто не использовал бы на практике, но я тебя точно ничем не ограничивал задавая вопрос о сортировке, и уж точно твоё "радикс и его варианты — единственный адекватный алгоритм." многое о тебе говорит. Большие данные ты сортировал чуть чаще чем никогда.

C>Ты так и не рассказал, чем так ужасен mmap.

я выше написал уже vsb, тем что генерирует на порядок больше i/o операций.
нормально делай — нормально будет
Re[7]: Вот так вот хипстеры сейчас на го сортируют
От: Codealot Земля  
Дата: 13.05.20 20:24
Оценка:
Здравствуйте, Мирный герцог, Вы писали:

МГ>но я тебя точно ничем не ограничивал задавая вопрос о сортировке


Если не сказано явно, что на требования по ресурсам нам насрать — используем более универсальное решение, а не то, которое работает только в очень узких условиях.

МГ>и уж точно твоё "радикс и его варианты — единственный адекватный алгоритм."


Для больших данных, в общем случае — да. Сортировку слиянием тоже можно, но это уже помедленнее.

МГ>я выше написал уже vsb, тем что генерирует на порядок больше i/o операций.


При каких условиях?
Ад пуст, все бесы здесь.
Re[8]: Вот так вот хипстеры сейчас на го сортируют
От: Мирный герцог Ниоткуда  
Дата: 13.05.20 20:42
Оценка:
Здравствуйте, Codealot, Вы писали:

C>Если не сказано явно, что на требования по ресурсам нам насрать — используем более универсальное решение, а не то, которое работает только в очень узких условиях.

конкретно по моему вопросу quicksort универсальней radix sort, counting sort быстрей radix sort.

МГ>>и уж точно твоё "радикс и его варианты — единственный адекватный алгоритм."

C>Для больших данных, в общем случае — да. Сортировку слиянием тоже можно, но это уже помедленнее.
как лихо у тебя "единственный адекватный" стал вдруг "для больших данных, в общем случае". Но проблески обучаемости налицо.

C>При каких условиях?

попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.
нормально делай — нормально будет
Re[9]: Вот так вот хипстеры сейчас на го сортируют
От: Codealot Земля  
Дата: 13.05.20 22:27
Оценка: +1
Здравствуйте, Мирный герцог, Вы писали:

МГ>конкретно по моему вопросу quicksort универсальней radix sort


В каком месте он универсальней? Единственные его плюсы — проще в реализации и работает быстрее на маленьких объемах.

МГ>counting sort быстрей radix sort.


В тех крайне редких случаях, когда его можно применить. Точнее говоря — практически не существующих в реальности случаях.

МГ>как лихо у тебя "единственный адекватный" стал вдруг "для больших данных, в общем случае".


Это и значит адекватный.

МГ>попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.


А зачем мне идти на собеседование в какую-то неизвестную шарашкину контору?
Ад пуст, все бесы здесь.
Re[10]: Вот так вот хипстеры сейчас на го сортируют
От: Мирный герцог Ниоткуда  
Дата: 14.05.20 05:30
Оценка: :)
Здравствуйте, Codealot, Вы писали:

МГ>>конкретно по моему вопросу quicksort универсальней radix sort

C>В каком месте он универсальней?

C>Единственные его плюсы — проще в реализации и работает быстрее на маленьких объемах.


МГ>>counting sort быстрей radix sort.

C>В тех крайне редких случаях, когда его можно применить. Точнее говоря — практически не существующих в реальности случаях.


МГ>>как лихо у тебя "единственный адекватный" стал вдруг "для больших данных, в общем случае".

C>Это и значит адекватный.


МГ>>попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.

C>А зачем мне идти на собеседование в какую-то неизвестную шарашкину контору?
твой уровень мне понятен, тебе — действительно незачем.
нормально делай — нормально будет
Re[2]: Вот так вот хипстеры сейчас на го сортируют
От: IID Россия  
Дата: 16.05.20 03:04
Оценка: +1
Здравствуйте, Философ, Вы писали:

Ф>Выбор mmf заставляет сильно сомневаться в его профессионализме: там у него последовательный доступ...


Какая разница какой доступ, MMF ничем не хуже обычного файла.
Даже лучше — чтение происходит гарантировано в целевую память. При обычном чтении, скорее всего, будет промежуточное копирование из ядра в юзермод.
kalsarikännit
Re[4]: Вот так вот хипстеры сейчас на го сортируют
От: IID Россия  
Дата: 16.05.20 03:10
Оценка:
Здравствуйте, Hobbes, Вы писали:

H>Здравствуйте, Мирный герцог, Вы писали:


МГ>>как бы ты например отсортировал 2^32 32-битных целых?


H>Сортировка подсчётом. Надо всего-то 16 Гб памяти


Если числа попарно-различные (или требуется это проверить) то хватит 128 мб.
kalsarikännit
Re[9]: Вот так вот хипстеры сейчас на го сортируют
От: IID Россия  
Дата: 16.05.20 03:11
Оценка:
Здравствуйте, Мирный герцог, Вы писали:

C>>При каких условиях?

МГ>попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.

Т.е. для ответа тебе сначала необходимо получить преимущество ?

А давай-ка наоборот!
На собеседовании сейчас ТЫ. Отвечай.
kalsarikännit
Re[5]: Вот так вот хипстеры сейчас на го сортируют
От: IID Россия  
Дата: 16.05.20 03:24
Оценка:
Здравствуйте, andrey.desman, Вы писали:

AD>Толку ноль от него, но и вреда столько же.


Толк очень простой — упрощение кода.
kalsarikännit
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.