Самый быстрый способ сортировки массива

← →
Sergey_R © (2005-10-25 15:15) [0]

Есть компонент StringGrid, в котором n столбцов и y строк. Надо быстро отсортировать все строки по какому-нибудь столбцу. Сделал сортировку пузырьков, но слишком уж долго думает, при больших y. Каким способом еще можно осуществить сортировку?

← →
clickmaker © (2005-10-25 15:21) [1]

http://www.yandex.ru/yandsearch?stype=&nl=0&text=%E0%EB%E3%EE%F0%E8%F2%EC%FB+%F1%EE%F0%F2%E8%F0%EE%E2%EA%E8

← →
MBo © (2005-10-25 15:22) [2]

QuickSort
исходник есть в Classes.pas и в Demos\Threads

← →
begin...end © (2005-10-25 15:29) [3]

При этом, ИМХО, лучше не хранить строки в самом гриде. Чтобы было быстрее, лучше использовать TDrawGrid (выводить текст самостоятельно), а данные хранить в отдельном массиве.

← →
Sergey_R © (2005-10-25 16:36) [4]

> При этом, ИМХО, лучше не хранить строки в самом гриде. Чтобы
> было быстрее, лучше использовать TDrawGrid (выводить текст
> самостоятельно), а данные хранить в отдельном массиве.

А почему? StringGrid вроде бы не сильно медленно обращается к строкам! Вот с TreeView я запарился, тот уж действительно тормоз!

← →
Defunct © (2005-10-25 19:27) [5]

Sergey_R © (25.10.05 16:36) [4]

> А почему?
Потому что StringGrid при изменении ячейки пытается ее перерисовать, а это целый воз дополнительных небыстрых операций.

Экперимента ради, создайте StringGrid, скормите ему больше 10 тыс строк. И попробуйте отсортировать. Потом проделайте тоже самое со StringList. И сравните время.

С уважением.

← →
Anatoly Podgoretsky © (2005-10-25 20:14) [6]

Он не долго думает, а долго перемещает, особенно если с отображением.

← →
wicked © (2005-10-25 22:23) [7]

а все потому, что у StringGrid неправильная идеология.... контрол не должен хранить данные, он должен их отображать.... вотъ.... :)
правильная - внешние источники данных, например, DBGrid как таковой, ListView с OwnerData = true, ListBox со Style = lbVirtual, GridView как таковой (не стандартный, но намного приятней стандартного грида)....
можно долго спорить о преимуществах и недостатках данного подхода, но, имхо, контрол, хранящий данные, сбивает с толку начинающих программистов....
сори за морализаторство.... ;)

← →
Alex Konshin © (2005-10-26 02:36) [8]

Look at my ArrayGrid on my homepage

← →
sniknik © (2005-10-26 08:25) [9]

обычно, когда мне нужен StringGrid (по типу) я беру вместо него датасет, чаще адошный, реже клиентский. (база не нужна! эти компоненты могут хранить данные в памяти).
т.е. вместо одного компонента (StringGrid) ложим три (ADODataSet, DataSource, DBGrid), работа с ним немного отличается (будет непривычно по первости), но вот если уж что и работает правильно с данными так это "базные" компоннты...
сортировка (индекс по полю) делается не в пример StringGrid-у (разница на порядки, т.е. если у StringGrid-а по милиону записей сортировку записей можно делать часы то в датасете это займет секунды...)
+ быстрее заполнение данными, хранение по типам а не только строки, фильтры, связи, отключение контролов на момент обработки данных и т.д. одни плюсы, а минус практически один и то поначалу - непривычна идеология если привык к стринггриду (в общем стоит поменять ;о))

← →
sniknik © (2005-10-26 09:12) [10]

вот примерные цифры (машины у всех разные, мои цифры на ваших точно не получатся ;)
есть у меня примерчик, датасета "как" стринггрид, по трем полям - целое, строка (50), дробное.
ток вот заполнение такого у меня идет (1 милион записей) - 10мин 38сек. ну тут надо учесть что данные генерятся, случайным образом, какой никакой а расчет... если считывать тоже самое с файла/стрима/другого датасета получится не впример быстрее... (а данные потому и данные что не расчитываются какждый раз случайно, а передаются откудато для обработки)
сортировка по этому лимону,
целое число - 5 сек (на самом деле четыре с мелочью ~ 4.78/91)
строка (тут самое длительное ;) - 36сек (таже фигня)
дробное - 6 сек (еще раз тоже самое ;)
можно добится тогоже от чистого StringGrid-а? ой, сомневаюсь... ;)
но это еще не все, т.к. это не просто сортировка а индексирование то по построеному индексу (второе обращение) время "сортировки" уже другое и равно во всех трех случаях ~ 0. (не. на самом деле время конечно какоето проходит на переключение индекса. но меряю я его таймером, и способ не "ловит" таких малых величин. можно конечно перейти тики компьютерные считать... но оно мне надо? ;о)))
короче подумай в этом направлении. ;) а еще сделай такой же тест для StringGrid-а... очень интересно реально сравнить. машину выбирай любую против моей старенькой (атлон зандербирд 1300. памяти 512). поможет думать. ;о))

← →
КиТаЯц © (2005-10-26 09:45) [11]

> Anatoly Podgoretsky © (25.10.05 20:14) [6]

Да.
Вопрос в догонку (вспомнил). Есть у стринггрида что-нибудь типа Begin(End)Update???

← →
sniknik © (2005-10-26 10:55) [12]

КиТаЯц © (26.10.05 09:45) [11]
неважно, возможно нет, скорее всего даже нет, но можно же заблокировать отрисовку всего окна
LockWindowUpdate(handle);
try
...
finally
LockWindowUpdate(0);
end;
но там кроме отрисовки куча строковых операций, по их перемещению, при сортировке, тоже не быстрых...

← →
Sergey_R © (2005-10-26 12:53) [13]

А если на время сортировки сделать StringGrid невидимым? Тогда он не будет перерисовывать ячейки, и сортировка пойдет гораздо быстрее?

← →
Alex Konshin © (2005-10-26 13:49) [14]

sniknik © (26.10.05 09:12) [10]
А ты все-таки посмотри на мой ArrayGrid. Он будет работать намного быстрее твоего варианта, да и работать с ним довольно просто.
Там в качестве примера как раз-таки тоже генерятся псевдо случайные данные и потом можно покликать на заголовки колонок, чтоб сортировать.
Мне несколько человек в разное писало, что они развивали эту идею и этот компонент дальше.

← →
sniknik © (2005-10-26 14:29) [15]

Alex Konshin © (26.10.05 13:49) [14]
заранее верю что так и есть, т.е. быстрее.
но тут уж что больше важнее функционал и ли скорость. с датасетом это (имхо) и то и другое. ну к примеру у тебя есть связки типа мастер-детайл между ArrayGrid-ами? а я к ним уже привык. ;)
впрочем все одно посмотрю. вечером, дома.

Sergey_R © (26.10.05 12:53) [13]
> А если на время сортировки сделать StringGrid невидимым?
сделай и проверь. но это лишнее, в sniknik © (26.10.05 10:55) [12] пример "локирования" формы от всех отрисовок, блокировать еще чтото дополнительно просто нельзя.

> Look at my ArrayGrid on my homepage

Да я ж адреса не знаю...

Посмотрии него в анкете. Там есть.

Alex Konshin © (26.10.05 13:49) [14]
посмотрел. время заполнения гораздо быстрее, у меня 9 сек на тот же лимон записей... (вместо 11 мин.)

остальное не так впечатляет.
строка (ну там где "item ...") 27 сек. (рекордсет 36сек)
целое (номер) 7 сек (рекордсет 5сек)
дробное - 10 сек. (рекордсет 6)

т.е. сортировка ~ на том же уровне. но!
в гриде то не сортировка а построение индекса, т.е. в рекордсете вернутся и отсортировать ранее сортированное поле времени не занимает вообще. у тебя же при возврате от сортировки по целому к сортировке по строке (поле сменить обратно) теже самые 27сек уходят...
и тоже самое время (27 сек) если порядок сортировки нужно сменить, в рекордсете смена порядка также времени не занимает.

в общем плюсов у рекордсета по моему всетаки больше. единственное слабое место это заполнение т.к. заполняется по одной записи. ну тут есть еще место для оптимизации (если это нужно), можно попробовать сделать с потока загружать (так же как передается при копировании рекордсета) подпихивать в том же формате. или еще что, придумать както пакетами данные добавлять. но это лишнее (имхо), получение данных с файла более частая операция чем тестовое заполнение, и она делается намного быстрее (сравнимо с твоими 9 сек.)
да и еще, я на самом деле вас немного обманул (ненамерено естественно), когда утром мерял у меня файл на скачке стоял... в обшем перепроверка на незанятой ничем машине показала заполнение 2 мин. тоже много но уже не так впечатляюща разница ;). а вот по сортировке практически теже цифры, что были.

а вообще, сам компанент конечно крутой. ;) наверняка можно найти применение.

> sniknik © (26.10.05 23:37) [18]
у грида того есть одно хорошее преимущество - он не data-aware, поэтому лишен того overhead"а (не знаю, как перевести, чтоб похоже было), который присущ всем data-aware компонентам...
имхо, конечно (ибо не глядел), но мнение выскажу...

> Посмотрии него в анкете. Там есть.

В какой еще анкете? Где она?

Постоянно использую стрингриды, в т.ч. и прерисовываемые.
При выборе его в качестве средства визуализации руководствуюсь след:
1. Кол-во строк не более 1000
2. Кол-во столбцов не более того, что может уместиться при распахнутой форме при 1024*768

Все, что отображается в стригриде, предварительно запихиваю в TList, где и сортирую при необходимости. Стринггрид просто перезаполняется простым перебором TList, в конце цикла устанавливается RowCount. Для особо "нагруженных" (часто и существенно обновляемых) стринггридов использую фрэймы, которые убиваю и создаю по новой, т.к. стрингрид не освобождает память при простом уменьшении RowCount (вот ука такая ;))

Перерисовка практически незаметна.

> Стринггрид просто перезаполняется простым перебором TList

А TList позволяет хранить несколько столбцов?
И заметна разница в скорости сортировки?

> сделай и проверь

Разницы нет никакой :-) Как видимый тормозит, так и невидимый...

Самый быстрый способ сортировки массива Найти похожие ветки