Автор | Сообщение |
|
| |
Пост N: 376
Зарегистрирован: 03.12.08
|
|
Отправлено: 14.03.18 12:40. Заголовок: Помогите с реализацией быстрого алгоритма построения Дерева
Замучился ускорять простую операцию ...... всего 1000 элементов , а скорость обработки - полторы минуты ..... :( Имеется массив со списком заказов вида : { { Название_Файла [C] , Дата_заказа [D] , Время [N] } , ... } отображение этого списка в виде дерева : Кто как разносил подобную информацию по узлам "дерева" ?
|
|
|
Ответов - 8
[только новые]
|
|
|
| |
Пост N: 6757
Зарегистрирован: 17.05.05
|
|
Отправлено: 14.03.18 15:21. Заголовок: Покажи свой алгоритм..
Покажи свой алгоритм для начала если он не шибко большой
|
|
|
|
| |
Пост N: 614
Зарегистрирован: 08.07.06
|
|
Отправлено: 14.03.18 17:13. Заголовок: Использую иерархию в..
Использую иерархию в группах товара со времен Clipper. В общих чертах - имеется "плоская" таблица Наименование группы C50 Краткое наименование C3 Путь С20 Родительская группа C3 Группа последняя? L1 Сначала сверху вниз проходим по всем группам, строим "путь" каждой группы внутри иерархии. Рекурсия, наподобие обработки файлов и вложенных директориев. Перестроение дерева делается почти мгновенно (доли секунд), групп и подгрупп товара - около 350. Потом делаем индекс по пути и плоская табличка становится "деревом". "Иерархия товара" обычному юзеру не видна, это я показал кусок окна редактирования/перестановки, когда одну группу/ветку нужно вложить/переместить в другую.
|
|
|
|
| |
Пост N: 377
Зарегистрирован: 03.12.08
|
|
Отправлено: 14.03.18 17:29. Заголовок: В том-то и дело что ..
В том-то и дело что навороченный ... Я сразу пошел не совсем рациональным путём .... что называется "в лоб"
|
|
|
|
| Администратор
|
Пост 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 Для формирования выходного массива можно использовать операции с хэш. Тоже это здесь обсуждалось.
|
|
|
|
| |
Пост N: 378
Зарегистрирован: 03.12.08
|
|
Отправлено: 14.03.18 22:18. Заголовок: Была мысль через DBF..
Была мысль через DBF с индексом сделать .... думал что медленно . Нашел в чем тормоз : ASCAN () при проверке уникальности элемента (и последующем добавлении в результирующий массив ) 1000 проверок в 5-размерном массиве и результирующем тоже на 1000 элементов мои компьютеры тратили примерно от 52 до 75 секунд . PS: есть-ли в Harbour функция "сжатия" массива - удаление пустых значений (NIL) ?
|
|
|
|
| |
Пост N: 6760
Зарегистрирован: 17.05.05
|
|
Отправлено: 14.03.18 23:15. Заголовок: Softlog86 пишет: A..
Softlog86 пишет: цитата: | ASCAN () при проверке уникальности элемента |
| Попробуй использовать Hash массив для проверки
|
|
|
|
| |
Пост N: 379
Зарегистрирован: 03.12.08
|
|
Отправлено: 14.03.18 23:50. Заголовок: Я с ними никогда не ..
Я с ними никогда не работал ... сходу не совсем понял как .
|
|
|
|
| Администратор
|
Пост 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
|
|
|
|