И снова о сортировке. - Форум на исходниках

WWW.ИСХОДНИКИ.РУ cpp.sources.ru

java.sources.ru web.sources.ru soft.sources.ru

jdbc.sources.ru asp.sources.ru api.sources.ru

  Форум на исходниках
  C / C++ / Visual C++
  И снова о сортировке.
СПРОСИТЬ  ОТВЕТИТЬ
профайл | регистрация | faq

Автор Тема:   И снова о сортировке.

Heromantor опубликован 11-10-2001 21:41 MSK
Может кто знает какой метод сортировки взят за основу в утилитке sort(эта такая стандартная в поставке вынь). Уж больно быстро она сортирует, один недостаток файлик в 50 мег уже не осилила :(. И еще как я понял сортировка слиянием одна из самых эффективных для файлов, так это или есть исчо какая нить? Я говорю не о вариантах сортировки слянием.
Michael опубликован 12-10-2001 01:04 MSK
Есть ещё метод Хоара ("быстрая сорт-ка"). Самый быстрый из тех, которые я знаю (знаю много).
Есть рекурсивный и нерекурсивный. В примерах к C++Builder5 входит примерчик потоков, где сравниваются пузырь, слиянием(?) и "быстрая".
Если надо алгоритм - мыль.
Читай Кнута и Вирта.
Heromantor опубликован 12-10-2001 01:34 MSK
Да я знаю быструю сортировку массив в 10000000 из DWORD сортирует за 15 секунд на Cel300. НО есть одно НО как я говорл нужна сортировка ФАЙЛА достаточно большого где-то мег на 500 :), исходя из того что копируеться этот файл у меня где-то минуты 3 то сортировка должна занимать НЕ БОЛЕЕ 10 минут. Кол-во строк где-то 20-30млн. Быстрая сортировка не позволяет эффективно кэшировать файл в память, а вот слияние это классно. 2 файла сливается за один проход! Можно кстати сделать сортировку слиянием с одним а не с 2 буферами? Кнут че-то писал об этом но у меня книжка в pdf без картинок ;), так что ничего не видно :(.
Kosha опубликован 12-10-2001 04:13 MSK
2Michael: Не всегда. На уже отсортированном массиве все эти методы типа QuickSort, Shell, вставками и им подобные уделываются простой выборкой
Kosha опубликован 12-10-2001 04:14 MSK
Опять же, если массив большой, или, наоборот, крохотный, если есть память лишняя или нет, если, если, если...
Тут нужно просто написать все и сравнить для конкретной задачи
Kosha опубликован 12-10-2001 04:16 MSK
2Neromantor: в Sort - обычный QuickSort, правда, целиком и полностью на асме ;-)
OlegO опубликован 12-10-2001 10:56 MSK
А мне казалось что сортировка бинарным деревом быстрее не придумать (если не считать подготовительной операции составит это дерево), или я ошибаюсь.
Heromantor опубликован 13-10-2001 02:03 MSK
2Kosha: Аааааа так если в sort исп. быстрая сортировка то как тогда там кэшировать данные? И вообще работать с файлом, прикол в том что файл очень не приятный :), у него каждая строка 2-10 байт => хеши, индексы просто не имеют смысла, до и памяти просто не хватит. Если есть у кого мысли как эффективно отсортировать БОЛЬШОЙ ФАЙЛ. Поделитесь плз.
Kosha опубликован 14-10-2001 01:55 MSK
Есть идейка одна...
Тебе не критично несколько проходов?
Просто можно сортировать блоками: сначала выбрать всё с одинаковой первой буквой и т.д.
Но это, соответственно, тоже в память надо грузить.
А вообще, если не критична скорость и быстрый винт, можно табличку сделать и маленькую функцию...
Туманно, наверное.
Короче: таблица ссылок на данные, читается все с диска, а сортируется сама таблица...
Потом обрабатывается...
Криво, блин! ;-)))
Heromantor опубликован 14-10-2001 04:13 MSK
Тебе не критично несколько проходов?
Просто можно сортировать блоками: сначала выбрать всё с одинаковой первой буквой и т.д.
Ты предлагаешь сторировать деревом? Как я понимаю. Я до этого исчо не дошел :), надо все методы по порядку перепробовать :).
А вообще, если не критична скорость и быстрый винт, можно табличку сделать и маленькую функцию...
Скорость критична и память критична ВСЕ критично :))))
Туманно, наверное.
Короче: таблица ссылок на данные, читается все с диска, а сортируется сама таблица...
Я делаю так: сканирую файл делаю индексы все строк в файле, т.е. позиция каждой строки в файле, а затем в ф-ции сортировки считываю эти строки и сравниваю ф-цией типа strcmp но моей, она побыстрее работает. И меняю соотв. сами индексы. Дело в том что при скажем быстрой сортировке кэшировать довольно трудно, может кэширование плохо построено, я кэширую по принципу что часто используемый элемент перемещаеться вверх, т.е. дольше остаеться в кэше, новый элемент добавляеться в конец. По моему для данной ситуации это приемлимо.
Valery опубликован 18-10-2001 11:06 MSK
to Heromantor:
а если построить массив из хэш-функций твоих строк (он будет многократно меньше) естественно с сохранением ссылок на строки в файле, сортировать спокойно в памяти, после этого уже перелопачивать сам файл. Не пойдет так?
migel опубликован 18-10-2001 23:22 MSK
BTree+ файл не потянет?
СПРОСИТЬ  ОТВЕТИТЬ
Перейти:

E-mail | WWW.ИСХОДНИКИ.RU

Powered by: Ultimate Bulletin Board, Freeware Version 5.10a
Purchase our Licensed Version- which adds many more features!
© Infopop Corporation (formerly Madrona Park, Inc.), 1998 - 2000.

Автор	Тема: И снова о сортировке.
Heromantor	опубликован 11-10-2001 21:41 MSK Может кто знает какой метод сортировки взят за основу в утилитке sort(эта такая стандартная в поставке вынь). Уж больно быстро она сортирует, один недостаток файлик в 50 мег уже не осилила :(. И еще как я понял сортировка слиянием одна из самых эффективных для файлов, так это или есть исчо какая нить? Я говорю не о вариантах сортировки слянием.
Michael	опубликован 12-10-2001 01:04 MSK Есть ещё метод Хоара ("быстрая сорт-ка"). Самый быстрый из тех, которые я знаю (знаю много). Есть рекурсивный и нерекурсивный. В примерах к C++Builder5 входит примерчик потоков, где сравниваются пузырь, слиянием(?) и "быстрая". Если надо алгоритм - мыль. Читай Кнута и Вирта.
Heromantor	опубликован 12-10-2001 01:34 MSK Да я знаю быструю сортировку массив в 10000000 из DWORD сортирует за 15 секунд на Cel300. НО есть одно НО как я говорл нужна сортировка ФАЙЛА достаточно большого где-то мег на 500 :), исходя из того что копируеться этот файл у меня где-то минуты 3 то сортировка должна занимать НЕ БОЛЕЕ 10 минут. Кол-во строк где-то 20-30млн. Быстрая сортировка не позволяет эффективно кэшировать файл в память, а вот слияние это классно. 2 файла сливается за один проход! Можно кстати сделать сортировку слиянием с одним а не с 2 буферами? Кнут че-то писал об этом но у меня книжка в pdf без картинок ;), так что ничего не видно :(.
Kosha	опубликован 12-10-2001 04:13 MSK 2Michael: Не всегда. На уже отсортированном массиве все эти методы типа QuickSort, Shell, вставками и им подобные уделываются простой выборкой
Kosha	опубликован 12-10-2001 04:14 MSK Опять же, если массив большой, или, наоборот, крохотный, если есть память лишняя или нет, если, если, если... Тут нужно просто написать все и сравнить для конкретной задачи
Kosha	опубликован 12-10-2001 04:16 MSK 2Neromantor: в Sort - обычный QuickSort, правда, целиком и полностью на асме ;-)
OlegO	опубликован 12-10-2001 10:56 MSK А мне казалось что сортировка бинарным деревом быстрее не придумать (если не считать подготовительной операции составит это дерево), или я ошибаюсь.
Heromantor	опубликован 13-10-2001 02:03 MSK 2Kosha: Аааааа так если в sort исп. быстрая сортировка то как тогда там кэшировать данные? И вообще работать с файлом, прикол в том что файл очень не приятный :), у него каждая строка 2-10 байт => хеши, индексы просто не имеют смысла, до и памяти просто не хватит. Если есть у кого мысли как эффективно отсортировать БОЛЬШОЙ ФАЙЛ. Поделитесь плз.
Kosha	опубликован 14-10-2001 01:55 MSK Есть идейка одна... Тебе не критично несколько проходов? Просто можно сортировать блоками: сначала выбрать всё с одинаковой первой буквой и т.д. Но это, соответственно, тоже в память надо грузить. А вообще, если не критична скорость и быстрый винт, можно табличку сделать и маленькую функцию... Туманно, наверное. Короче: таблица ссылок на данные, читается все с диска, а сортируется сама таблица... Потом обрабатывается... Криво, блин! ;-)))
Heromantor	опубликован 14-10-2001 04:13 MSK Тебе не критично несколько проходов? Просто можно сортировать блоками: сначала выбрать всё с одинаковой первой буквой и т.д. Ты предлагаешь сторировать деревом? Как я понимаю. Я до этого исчо не дошел :), надо все методы по порядку перепробовать :). А вообще, если не критична скорость и быстрый винт, можно табличку сделать и маленькую функцию... Скорость критична и память критична ВСЕ критично :)))) Туманно, наверное. Короче: таблица ссылок на данные, читается все с диска, а сортируется сама таблица... Я делаю так: сканирую файл делаю индексы все строк в файле, т.е. позиция каждой строки в файле, а затем в ф-ции сортировки считываю эти строки и сравниваю ф-цией типа strcmp но моей, она побыстрее работает. И меняю соотв. сами индексы. Дело в том что при скажем быстрой сортировке кэшировать довольно трудно, может кэширование плохо построено, я кэширую по принципу что часто используемый элемент перемещаеться вверх, т.е. дольше остаеться в кэше, новый элемент добавляеться в конец. По моему для данной ситуации это приемлимо.
Valery	опубликован 18-10-2001 11:06 MSK to Heromantor: а если построить массив из хэш-функций твоих строк (он будет многократно меньше) естественно с сохранением ссылок на строки в файле, сортировать спокойно в памяти, после этого уже перелопачивать сам файл. Не пойдет так?
migel	опубликован 18-10-2001 23:22 MSK BTree+ файл не потянет?