Отправлено: 14.03.18 12:40. Заголовок: Помогите с реализацией быстрого алгоритма построения Дерева

Замучился ускорять простую операцию ...... всего 1000 элементов , а скорость обработки - полторы минуты ..... :(
Имеется массив со списком заказов вида :
{ { Название_Файла [C] , Дата_заказа [D] , Время [N] } , ... }

отображение этого списка в виде дерева :



Кто как разносил подобную информацию по узлам "дерева" ?

 Отправлено: 14.03.18 15:21. Заголовок: Покажи свой алгоритм..

Покажи свой алгоритм для начала если он не шибко большой

 Отправлено: 14.03.18 17:13. Заголовок: Использую иерархию в..

Использую иерархию в группах товара со времен Clipper.



В общих чертах - имеется "плоская" таблица

 
 Наименование группы      C50 
 Краткое наименование    C3 
 Путь                   С20 
 Родительская группа     C3 
 Группа последняя?       L1

Сначала сверху вниз проходим по всем группам, строим "путь" каждой группы внутри иерархии. Рекурсия, наподобие обработки файлов и вложенных директориев.
Перестроение дерева делается почти мгновенно (доли секунд), групп и подгрупп товара - около 350.
Потом делаем индекс по пути и плоская табличка становится "деревом".
"Иерархия товара" обычному юзеру не видна, это я показал кусок окна редактирования/перестановки, когда одну группу/ветку нужно вложить/переместить в другую.

 Отправлено: 14.03.18 17:29. Заголовок: В том-то и дело что ..

В том-то и дело что навороченный ...
Я сразу пошел не совсем рациональным путём .... что называется "в лоб"

 Отправлено: 14.03.18 17:55. Заголовок: В цикле по исходному..

В цикле по исходному массиву надо построить результирующий массив вида:

{{Год1, {{Месяц1, {{День1, {{Заказ1,...},...}}, ...}}, ...}},...}

Результирующий массив сразу в процессе обработки должен быть отсортирован.

Как это сделать ? Когда-то на эту тему здесь было обсуждение:

http://clipper.borda.ru/?1-0-0-00000475-000-0-0-1276757268

Для формирования выходного массива можно использовать операции с хэш. Тоже это здесь обсуждалось.

 Отправлено: 14.03.18 22:18. Заголовок: Была мысль через DBF..

Была мысль через DBF с индексом сделать .... думал что медленно .
Нашел в чем тормоз : ASCAN () при проверке уникальности элемента (и последующем добавлении в результирующий массив )
1000 проверок в 5-размерном массиве и результирующем тоже на 1000 элементов мои компьютеры тратили примерно от 52 до 75 секунд .

PS: есть-ли в Harbour функция "сжатия" массива - удаление пустых значений (NIL) ?

 Отправлено: 14.03.18 23:15. Заголовок: Softlog86 пишет: A..

Softlog86 пишет:

цитата:

ASCAN () при проверке уникальности элемента

Попробуй использовать Hash массив для проверки

 Отправлено: 14.03.18 23:50. Заголовок: Я с ними никогда не ..

Я с ними никогда не работал ... сходу не совсем понял как .

 Отправлено: 15.03.18 09:21. Заголовок: Softlog86 пишет: На..

Softlog86 пишет:

цитата:

Нашел в чем тормоз : ASCAN () при проверке уникальности элемента (и последующем добавлении в результирующий массив ) 1000 проверок в 5-размерном массиве и результирующем тоже на 1000 элементов мои компьютеры тратили примерно от 52 до 75 секунд .

В старой теме, на которую я дал ссылку, в постах 1315, 1316 есть сырцы функций ascanas и asorta
ascanas - быстрый поиск значения в отсортированном массиве
asorta - сортировка двумерного массива.

Выходной массив надо сразу делать отсортированным с помощью той же функции ascanas. Тогда и поиск в нем будет быстрым. Пример как это сделать есть в функции T4
Впрочем, вашу задачу сразу можно упростить, если отсортировать исходный массив по дате (второму индексу):
ASORTA(ar, 2)
или по дате и времени:
ASORTA(ar, 2, 3)

Тогда в выходном массиве поиск можно не делать, а сравнивать только последний элемент. Если он совпадает - использовать его, если нет - добавлять новый.
Впрочем, и исходный массив лучше сразу формировать отсортированным, тогда и сортировка не понадобится.

цитата:

PS: есть-ли в Harbour функция "сжатия" массива - удаление пустых значений (NIL) ?

Нет. Только полным перебором массива. Что-то вроде:

i := 1
while i <= len(ar)
if ar[ i ] == nil
hb_adel(ar, i, .t.)
else
i ++
endif
enddo

А еще лучше изначально делать массив без nil