On-line:гостей 1. Всего: 1 [подробнее..]
АвторСообщение



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


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

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



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





Спасибо: 0 
ПрофильЦитата Ответить
Ответов -8 [только новые]


администратор




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


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

Спасибо: 0 
ПрофильЦитата Ответить





Пост N:614
Зарегистрирован:08.07.06
ссылка на сообщение  Отправлено:14.03.18 17:13.Заголовок:Использую иерархию в..


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



В общих чертах - имеется "плоская" таблица
 
Наименование группы C50
Краткое наименование C3
Путь С20
Родительская группа C3
Группа последняя? L1


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



Спасибо: 0 
ПрофильЦитата Ответить



Пост N:377
Зарегистрирован:03.12.08
ссылка на сообщение  Отправлено:14.03.18 17:29.Заголовок:В том-то и дело что ..


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




Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Пост N:3703
Зарегистрирован:23.05.05
ссылка на сообщение  Отправлено:14.03.18 17:55.Заголовок:В цикле по исходному..


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

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

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

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

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

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

Спасибо: 1 
ПрофильЦитата Ответить



Пост N:378
Зарегистрирован:03.12.08
ссылка на сообщение  Отправлено:14.03.18 22:18.Заголовок:Была мысль через DBF..


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

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






Спасибо: 0 
ПрофильЦитата Ответить
администратор




Пост N:6760
Зарегистрирован:17.05.05
ссылка на сообщение  Отправлено:14.03.18 23:15.Заголовок:Softlog86 пишет: A..


Softlog86 пишет:

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


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

Спасибо: 0 
ПрофильЦитата Ответить



Пост N:379
Зарегистрирован:03.12.08
ссылка на сообщение  Отправлено:14.03.18 23:50.Заголовок:Я с ними никогда не ..


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

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Пост N:3706
Зарегистрирован:23.05.05
ссылка на сообщение  Отправлено: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

Спасибо: 1 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
-участник сейчас на форуме
-участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 508
Права: смайлыда,картинкида,шрифтыда,голосованиянет
аватарыда,автозамена ссылоквкл,премодерацияоткл,правканет