Форум » [x]Harbour » Помогите с реализацией быстрого алгоритма построения Дерева » Ответить
Помогите с реализацией быстрого алгоритма построения Дерева
Softlog86: Замучился ускорять простую операцию ...... всего 1000 элементов , а скорость обработки - полторы минуты ..... :( Имеется массив со списком заказов вида : { { Название_Файла [C] , Дата_заказа [D] , Время [N] } , ... } отображение этого списка в виде дерева : Кто как разносил подобную информацию по узлам "дерева" ?
Ответов - 8
Dima: Покажи свой алгоритм для начала если он не шибко большой
Sergy: Использую иерархию в группах товара со времен Clipper. В общих чертах - имеется "плоская" таблица [pre2] Наименование группы C50 Краткое наименование C3 Путь С20 Родительская группа C3 Группа последняя? L1[/pre2] Сначала сверху вниз проходим по всем группам, строим "путь" каждой группы внутри иерархии. Рекурсия, наподобие обработки файлов и вложенных директориев. Перестроение дерева делается почти мгновенно (доли секунд), групп и подгрупп товара - около 350. Потом делаем индекс по пути и плоская табличка становится "деревом". "Иерархия товара" обычному юзеру не видна, это я показал кусок окна редактирования/перестановки, когда одну группу/ветку нужно вложить/переместить в другую.
Softlog86: В том-то и дело что навороченный ... Я сразу пошел не совсем рациональным путём .... что называется "в лоб"
Pasha: В цикле по исходному массиву надо построить результирующий массив вида: {{Год1, {{Месяц1, {{День1, {{Заказ1,...},...}}, ...}}, ...}},...} Результирующий массив сразу в процессе обработки должен быть отсортирован. Как это сделать ? Когда-то на эту тему здесь было обсуждение: http://clipper.borda.ru/?1-0-0-00000475-000-0-0-1276757268 Для формирования выходного массива можно использовать операции с хэш. Тоже это здесь обсуждалось.
Softlog86: Была мысль через DBF с индексом сделать .... думал что медленно . Нашел в чем тормоз : ASCAN () при проверке уникальности элемента (и последующем добавлении в результирующий массив ) 1000 проверок в 5-размерном массиве и результирующем тоже на 1000 элементов мои компьютеры тратили примерно от 52 до 75 секунд . PS: есть-ли в Harbour функция "сжатия" массива - удаление пустых значений (NIL) ?
Dima: Softlog86 пишет: ASCAN () при проверке уникальности элемента Попробуй использовать Hash массив для проверки
Softlog86: Я с ними никогда не работал ... сходу не совсем понял как .
Pasha: 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
полная версия страницы