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

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

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

Анализ строк в TStringList

RedLeo © (2006-07-26 17:39:00)
Есть такая проблема:
Существует список(TStringList) примерно из 300000 строк следующего вида:
имя=значение
как быстро создать на его основе 2 списка, один из которых составляется по следующему правилу: Если элемент с именем не существует в результирующем списке, то добавить его в противном случае добавить только значение. " список представляет собой только список имен результирующего.
Пример:
Исходный список:
Имя1=1
Имя2=2
Имя3=3
Имя1=5
Имя2=6
В результате получаются 2 списка:
Первый:
Имя1=1 5
Имя2=2 6
Имя3=3
Второй:
Имя1
Имя2
Имя3

Пытался решить задачу простым перебором строк в списке - получилось очень долго (8 секуед на 100 записей)
Вот, мое решение:
. . . if source.Count>0 then for i:=0 to source.Count-1 do begin end; s:=source.Names[i]; if outList.Values[s]='' then begin outList.add(source[j]); nameList.Add(ansiLowerCase(s)) end else outList.Values[s]:=outList.Values[s]+' '+ source.ValueFromIndex[i]; end; . . .
Пожалуйста, помогите оптимизировать код и ускорить данный процесс.

Ketmar (2006-07-27 14:50:00) [1]
>tesseract © (26.07.06 21:56) [9]
так не диссертация же нужна. а использование. я вот RBT использую не первый год -- нареканий никаких. %-)

atruhin (2006-07-27 00:17:00) [2]
Если этот словарь твой, то лучше всего его отсортировать один раз, а далее загружать уже отсортированный.
Если нет, то или B-tree, или Hash таблицы. Готовых алгоритмов в сети масса.
И в любом случае отказаться от outList.Values и подобного, использую динамические записи.

tesseract (2006-07-26 21:56:00) [3]
> [5] Ketmar © (26.07.06 19:04)

лучше B-tree они лучше изучены.

Мефисто (2006-07-26 20:44:00) [4]

> Ketmar © (26.07.06 19:04) [5]

Ты еще на труды Дональда Кнута намекни :) Математики - вагон и маленькая тележка.

default (2006-07-26 19:13:00) [5]
vain © (26.07.06 19:10) [6]
красно-чёрные деревья
сделай поиск

vain (2006-07-26 19:10:00) [6]

> предлагаю использовать другую структуру

Что такое Red-Black Tree?

Ketmar (2006-07-26 19:04:00) [7]
предлагаю использовать другую структуру для хранения данных. например, Red-Black Tree, в котором хранятся записи с некоторой информацией.
как? подумайте, намёк я дал.

Джо (2006-07-26 18:26:00) [8]
Разумеется, нужно будет использовать IndexOf для поиска существующего значения.

jack128 (2006-07-26 18:26:00) [9]
RedLeo (26.07.06 17:39)
откажись от использования свойства Values - это вечный тормоз.

Джо (2006-07-26 18:25:00) [10]
"Малой кровью" можно немного ускорить процесс, использовав THashedStringList (IniFiles, кажется) вместо TStringList. Там для сравнения используются хэши строк. Естественно, придется смириться с увеличением накладных расходов на память.

vain (2006-07-26 18:19:00) [11]
Надо отсортировать исходный список по полю Name, тогда в списке сначала будут все строки с ИМЯ1, потом с ИМЯ2... и т. д. Сложность quick sort'а - N*log2(N). Да ещё умнож это выражение на среднюю длину строки L. Вот и получается: L*N*log2(N) действий. (Придётся тебе вспомнить быстую сортировку) это примерно 5'500'000*L. Мне кажется, ничего быстрее придумать нельзя.

Наверх

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