Войти
ФлеймФорумПрограммирование

Задачка по алгоритмам (4 стр)

Страницы: 1 2 3 4
#45
23:05, 30 ноя. 2018

}:+()___ [Smile]
Вроде так:
https://rextester.com/RRTPPH86994

Комментарии:
0. Не тестировал.
1. Сложность (вроде) O(log2 N). Это достаточно "псевдоконстантно"? Возможно более хитрое дерево этому поможет.
2. Удаление - no-op. Вроде это не противоречит твоим требованиям, но память лишнюю жрёт. В т. ч. на промежуточные строки, возникающие в ходе работы. Возможно рефкаунт этому поможет.
3. O(log N) сравнение вроде тоже прикручивается.
4. handle наверное, лишние, достаточно Node*.


#46
23:53, 30 ноя. 2018

Стоп, походу гоню. concat/substr выполняют потенциально O(N) работы.

#47
0:15, 1 дек. 2018

FordPerfect
> потенциально
Это если дерево выродится в список?
А надо чтоб логарифм был в среднем, или в худшем случае?

#48
0:19, 1 дек. 2018

А как такое? Двунаправленное 256-арное дерево, любые строки/слайсы в нем указываются путем указания НЕ НА НАЧАЛО, А НА КОНЕЦ строки/слайса + длина. Для оптимизации операции substr для любых строк(и может быть слайсов, см. про противоречие ниже), добавлять оптимизирующую структуру, на которую должен быть указатель из последней позиции строки (или даже любого когда-либо взятого слайса).

Противоречие:

    String(const char *str, size_t len);            // O(len*log(S))
    ....
    String operator + (const String &str) const;    // O(log(S)), противоречит конструктору
    String substr(size_t start, size_t len) const;  // O(log(S)), противоречит конструктору

Операции конкатенации и взятия слайса фактически содержат в себе конструктор новой строки, для которого дозволено O(len*log(S)) (то есть, надо доопределить, должны ли эти операции вставлять свой результат в коллекцию или нет). Фактически противоречие здесь даже не в постановке, а в самой попытке оптимального храниения - если часть поддерева принадлежит больше, чем одной строке, то вставка такого слайса в коллекцию как самостоятельной строки однозначно потребует копирования всех элементов слайса., то есть len* .

P.S. Кстати, уже вставленные строки фактически иммутабельны, что упрощает дело с оптимизирующими структурами. Скажем, можно тупо добавить массивы указателей на все элементы дерева, участвующие в строке, в прямом порядке.

P.P.S. Вот, подумал, можно сделать ленивую операцию лексикографического сравнения. То есть, объект String, полученный в виде слайса, может оставаться таковым (с флагом "слайс") до тех пор, пока к нему не попытаются применить операцию лексикографического сравнения - тогда уже по честному вставлять его в коллекцию и убирать флаг "слайс". И да, у таких ленивых слайсов можно использовать в качестве оптимизирующей структуры слайс от исходной строки же.

#49
1:25, 1 дек. 2018

Блин, все вышенаписанное бесполезно, т.к. просто лексикографически сравнить строки - быстрее в любом случае, чем возиться с такой "задом-наперед" коллекцией...

P.S.
И, кстати, да, получается никакие варианты префиксных деревьев не катят поэтому. Ах, ну да, это топикстартер еще на первой странице написал...

#50
3:40, 1 дек. 2018

1 frag / 2 deaths
Не, это, походу, в среднем. O(1), O(log N) только если повезёт.
В список оно как раз не вырождается. Канонизация (как я её определил) приводит к постоянным перебалансировкам:
https://rextester.com/BZGOJY54412

#51
7:11, 1 дек. 2018

MrShoor
> Ну если тебе ropes подходят, и подходит амартизированное время, то мне кажется достаточно просто к каждому сегменту добавить и хранить хеш.
Не понял, зачем хеш? Ropes с рефкаунтами на каждую ноду и кастомный аллокатор, который отложенно удаляет иерархию, уже дает все, кроме операций сравнения.

> Единственное, что не вписывается сюда пока, так это лексикографическое сравнение и выделение подстроки.
С подстроками у Ropes никаких проблем, вроде, а вот со сравнениями...

В принципе, сравнения не прям так уж критичны, так что задача-минимум уже, можно сказать, решена.

FordPerfect
> Стоп, походу гоню. concat/substr выполняют потенциально O(N) работы.
Возьмем подстроку диной 7/8 исходной. Тогда все, кроме последних 3-х уровней дерева уменьшатся целиком, т. е. изменится длина 1/8 всех нод дерева, которое O(n).
Т. е. представление не позволяет сделать быстрее, а у тебя в алгоритме еще дополнительная рекурсия из-за вложенных prefix/concat.

> Сложность (вроде) O(log2 N). Это достаточно "псевдоконстантно"?
Да. Псевдоконстантно — это когда быстрее любой, сколь угодно малой, положительной степени.

> Удаление - no-op. Вроде это не противоречит твоим требованиям, но память лишнюю жрёт.
Да, это надо расширить условие: не должно жрать памяти больше, чем O(Smax), где Smax — суммарная длина активных строк в худший момент времени.
В общем, при непрерывной работе с наборами строк ограниченного размера потребление памяти не должно бесконтрольно расти.
Но что делать с удалением уже понятно: рефкаунты в ноды + отложенная деаллокация иерархии.
Надо только чтобы листовые и обычные ноды дерева были примерно одного размера.

1 frag / 2 deaths
> А надо чтоб логарифм был в среднем, или в худшем случае?
Надо в худшем. Собственно, задача именно в стабильном времени выполнения операций, независимо от длины строк.

Dmitry_Milk
> Операции конкатенации и взятия слайса фактически содержат в себе конструктор новой строки
Конструкторы бывают и приватные.

#52
12:25, 1 дек. 2018

}:+()___ [Smile]
Для чего применять то такое чудо собрался?

#53
12:38, 1 дек. 2018

}:+()___ [Smile]
> Конструкторы бывают и приватные.

Я не про это. Ведь сама идея собрать строки в некую коллекцию возникла ради того, чтобы ускорить операции лексикографического сравнения (остальные операции типа конкатенации или слайса не требуют этого, для них в случае иммутабельности достаточно лишь того, что объекты строк будут шарить свои данные).
Так вот в случае получения новой строки в результате слайса или конкатенации, они должны также быть добавлены в коллекцию как самостоятельные строки с НОВЫМИ отношениями лексикографического порядка с другими строками коллекции (а не с имевшимися до этого отношениями с другими подстроками исходной строки). То есть, по сути необходимо выполнить действия конструктора добавления новой строки в коллекцию (ну или лениво отложить на потом).

#54
19:25, 1 дек. 2018

*Lain*
> Для чего применять то такое чудо собрался?
Долго рассказывать. Вкратце, для того, чтобы сделать элементарные операции виртуальной машины на основе строкового стека действительно элементарными.

Dmitry_Milk
> Ведь сама идея собрать строки в некую коллекцию возникла ради того, чтобы ускорить операции лексикографического сравнения
Не надо придумывать задачу за меня. Лексикографическое сравнение является желательной, но не обязательной, операцией и я уже придумал, как можно обойтись без него.

> Так вот в случае получения новой строки в результате слайса или конкатенации, они должны также быть добавлены в коллекцию
В корне неверное понимание задачи. Результаты операций должны возникать внутри коллекции, а не добавляться отдельно.

#55
20:42, 2 дек. 2018

Возникла новая идея:
Строка хранится как набор блоков фиксированной длины с перекрытиями, примерно так:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
--------------------------
ABCDEFGH
      GHIJKLMN
          KLMNOPQR
                  STUVWXYZ
Блоки дедуплицируются, верхние уровни дерева строятся рекурсивно аналогичным способом.

Основная проблема тут — из всех возможных смещений выбрать те, которые будут хранится.
Чтобы удовлетворить требованиям к производительности надо, чтобы решение хранить блок зависело только от локальной окрестности этого блока в строке.
Т. е. нужна булева функция, которая принимает последовательность символов блока и контекста вокруг него и возвращает признак, нужно ли его хранить или нет.
Эта функция, с одной стороны, должна гарантировать максимальное расстояние между соседними true не больше размера блока, а с другой — ограничить среднюю плотность блоков снизу.
Соответственно, вопрос: можно ли построить такую булеву функцию?

Страницы: 1 2 3 4
ФлеймФорумПрограммирование

Тема в архиве.