Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: 1 2 >
Sergey_R © (2005-10-25 15:15:00)
Есть компонент StringGrid, в котором n столбцов и y строк. Надо быстро отсортировать все строки по какому-нибудь столбцу. Сделал сортировку пузырьков, но слишком уж долго думает, при больших y. Каким способом еще можно осуществить сортировку?

Sergey_R (2005-10-27 17:42:00) [1]
> Стринггрид просто перезаполняется простым перебором TList

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

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

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

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

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

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

Sergey_R (2005-10-27 11:06:00) [3]

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

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

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

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

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

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

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

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

Amoeba (2005-10-26 16:06:00) [6]
Посмотрии него в анкете. Там есть.

Sergey_R (2005-10-26 15:40:00) [7]

> Look at my ArrayGrid on my homepage

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

sniknik (2005-10-26 14:29:00) [8]
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] пример "локирования" формы от всех отрисовок, блокировать еще чтото дополнительно просто нельзя.

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

Sergey_R (2005-10-26 12:53:00) [10]
А если на время сортировки сделать StringGrid невидимым? Тогда он не будет перерисовывать ячейки, и сортировка пойдет гораздо быстрее?

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

КиТаЯц (2005-10-26 09:45:00) [12]

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

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

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

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

Alex Konshin (2005-10-26 02:36:00) [15]
Look at my ArrayGrid on my homepage

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

Anatoly Podgoretsky (2005-10-25 20:14:00) [17]
Он не долго думает, а долго перемещает, особенно если с отображением.

Defunct (2005-10-25 19:27:00) [18]
Sergey_R © (25.10.05 16:36) [4]

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

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

С уважением.

Sergey_R (2005-10-25 16:36:00) [19]

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

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

begin...end (2005-10-25 15:29:00) [20]
При этом, ИМХО, лучше не хранить строки в самом гриде. Чтобы было быстрее, лучше использовать TDrawGrid (выводить текст самостоятельно), а данные хранить в отдельном массиве.

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »