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

← →
RedLeo (2006-07-26 17:39) [0]

Есть такая проблема:
Существует список(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; . . .
Пожалуйста, помогите оптимизировать код и ускорить данный процесс.

← →
vain © (2006-07-26 18:19) [1]

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

← →
Джо © (2006-07-26 18:25) [2]

"Малой кровью" можно немного ускорить процесс, использовав THashedStringList (IniFiles, кажется) вместо TStringList. Там для сравнения используются хэши строк. Естественно, придется смириться с увеличением накладных расходов на память.

← →
Джо © (2006-07-26 18:26) [3]

Разумеется, нужно будет использовать IndexOf для поиска существующего значения.

← →
jack128 © (2006-07-26 18:26) [4]

RedLeo (26.07.06 17:39)
откажись от использования свойства Values - это вечный тормоз.

← →
Ketmar © (2006-07-26 19:04) [5]

предлагаю использовать другую структуру для хранения данных. например, Red-Black Tree, в котором хранятся записи с некоторой информацией.
как? подумайте, намёк я дал.

← →
vain © (2006-07-26 19:10) [6]

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

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

← →
default © (2006-07-26 19:13) [7]

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

← →
Мефисто (2006-07-26 20:44) [8]

Если этот словарь твой, то лучше всего его отсортировать один раз, а далее загружать уже отсортированный.
Если нет, то или B-tree, или Hash таблицы. Готовых алгоритмов в сети масса.
И в любом случае отказаться от outList.Values и подобного, использую динамические записи.

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

Анализ строк в TStringList Найти похожие ветки