Здравствуйте. У меня есть некоторое линейное пространство целых чисел N: ------------------------------ в этом пространстве можно рисовать линии, например, так: ---=========--------------- параметры всех линий хранятся в табличке [{line_start, line_end}] если я рисую линию в том месте, где уже нарисовано - линии должны сливаться: было нарисовано: [{5, 8}, {9, 11}] рисую новую линию: [{8, 10}] должно получиться: [{5, 11}] Вот я думаю о реализации. По видимому, нужно создавать упорядоченную мапу std::map<uint, uint>, в которой ключ - адрес первой закрашенной ячейки, значение - адрес последней закрашенной ячейки некоторой линии. При вставке нового элемента проверять его пересечение с соседними. Если есть пересечения, то удалять, изменять размер. Совсем простая реализация std::vector<bool>, но, с точки зрения объёма потребляемой памяти и эффективности кода - не самая лучшая. Какие ещё варианты?
Прошей табличку двумя списками (с принудительной связью), один будет представлять собою отрезки отсортированные по началу, второй -- по концу. Дальше найти те отрезки, которые пересекаются с данным -- несложно. Если же, при этом, лень перебирать все элементы от начала списков до нужного, то замени списки на бинарные отсортированные деревья. Хотя нет. Такое лобовое решение не лучшее. Есть другой вариант. Проще. А с учётом того, что тебе неинтересно хранить исходные отрезки, то проще гораздо. Просто храни список "непрерывных" отрезков, непрерывных в том смысле, что между началом и концом отрезка все точки входят в этот отрезок. Список этот будет сортироваться единственным образом. И можно запросто найти в нём в какой из отрезков попадёт та или иная точка. Соответственно добавление нового отрезка будет элементарно: 1. найти самый левый отрезок, чей правый конец лежит правее левого конца добавляемого отрезка 2. найти самый правый отрезок, чей левый конец лежит левее правого конца добавляемого отрезка 3. удалить из списка все отрезки начиная с найденного в п.1 и заканчивая найденным в п.2 4. вставить на место удалённых отрезков новый, чьи начало и конец высчитываются функциями min/max на концах добавляемого отрезка и найденных в п.1 и п.2 (мне лень формулировать, по-хорошему надо бы обозначения какие-то ввести, иначе мозг плывёт от таких фраз) [nb. "правый" и "левый" я употребляю в смысле расположения на числовой оси] Если операция линейного поиска по списку будет слишком медленной, то список можно заменить прошитым деревом.
srm Лучше множество линий (если я правильно понял, речь идёт об интервалах, т.к. пространство одномерное) хранить в обычном множестве, а для самих интервалов переопределить оператор сравнения: Код (Text): class Interval { public: inline Interval (DWORD start, DWORD size); bool operator< (Interval const &interval) const { return start + size < interval.start; } private: DWORD start, size; }; Interval::Interval(DWORD start, DWORD size) { Interval::start = start; Interval::size = size; } std::set <Interval> intervals; Здесь хранится не начало и конец, а начало и размер, чтобы исключить вариант, когда начало больше конца. Кроме того немного нарушена транзитивность равенства, но это нестрашно. Тогда с помощью find+erase можно перечислить и удалить все интервалы, пересекаемые вставляемым, попутно модифицируя вставляемый интервал. Когда все пересекающие интервалы будут удалены, модифицированный интервал можно вставить в множество.
Это не принципиально. Если алгоритм составлен правильно, то такая ситуация будет невозможна. С другой стороны, и размер может получиться отрицательным. Зачем удалять? Я хочу просто вставлять элементы. В начале таблица пуста, значит и пересечений нет. Нужно просто алгоритм вставки грамотно составить. что-то я не понимаю: что это даёт?
srm Не принципиально, но лучше исключить возможность ошибки, чем думать потом, как бы её не сделать. DWORD — беззнаковый тип. Согласно Вашему же примеру: в процесс вставки должно входить удаление пересекаемых элементов. Грамотный алгоритм вставки описан последним абзацем поста #4. То, что не нужно искать, какие линии пересекаются вставляемыми. std::set, в частности find, сделает это за Вас.
я так понял, пересекаюшихся значений не предвидится. тогда почему б не использовать простой сортированный массив с дополнительным недействительным значением для ускорения операций? искать можно и перебором, и половинным делением
l_inc тем хуже - получится что-нибудь типа 0xFFFFFFF3. Да, возможно. Нужно подумать. Кстати, std::set использовать нельзя - он не позволяет изменять элементы, нужно std::map; Вставка элемента ~n. В дерево ~ln(n).
А в каком случае получится, что end < start? Ну да. В случие с сетами придётся удалять старый/вставлять новй элемент. Ну допустим такая ситуация: в таблице [{3, 5}] рисуем линию {4, 6}. Нужно будет сначала в цикле find/erase (каждый по ~ln(n)), затем insert (тоже ~ln(n)). Хотя, зная, что если есть пересекающиеся элементы, то они лежат рядом, то можно только 1 раз вызвать insert (~ln(n)) и далее проверить соседние с ним элементы.
га? я ж вам говорю - разреженный массив с недействительными значениями. те, раздвижка будет только до 1го недействительного с его поглошением. иногда, правда, при сильно длинных раздвижках придется зановлять весь массив заново его разбавляя можете еще использовать список списков. скажем, ((a, b, &arr0[]), (b, c, &arr1[]), ...итд) можете и дерево. только это будет больше кода и памяти. да и выродиться может
srm В том случае, если Вы передадите его так в конструктор. operator< будет неверно работать с таким интервалом. Если же Вы в качестве размера передадите 0xFFFFFFF3, то operator< будет работать правильно, просто интервал очень большой. Хотя, конечно, можно внутрь operator< добавить дополнительную проверку на то, что меньше: end или start. В общем, я просто пояснил, почему использовал в своём примере start и size, а не start и end, хотя это действительно непринципиально. Не обязательно для поиска каждого пересекающегося элемента делать find. Можно чуть усложнить и делать find только для первого, после чего пройтись вперёд полученным итератором, пока не попадётся неравный интервал. Но в результате это тот же O(log n). [obsolete] В любом случае, даже если Вы не хотите удалять какой-то из пересечённых интервалов, чтобы сэкономить на последнем insert, то find возвращает неконстантный итератор. Так что модифицируйте на здоровье. Только смотрите, чтобы это не привело к рассинхронизации всего дерева. [/obsolete] Не. Извиняюсь. Не туда глянул. Итератор константный. Предыдущий абзац не имеет смысла.
srm попробуйте деревом. только сразу учтите, что новый отрезок вполне может перекрывать > 2х старых. и начальная и конечная точки могут не совпадать с началом и концом старых. и даже не лежать на теле старых отрезков. те (2, 88) перекроет ((3, 5), (8, 12), (44, 55), (78, 79))
srm, есть один очень хитрый и весьма быстрый вариант, если начала/концы - целые 32-битные. Правда требует один гигабайт памяти, но сейчас такие объемы вроде не проблема. Заводите две битовые карты по 512 метров. Обнуляете их. Далее цикл по заданным отрезкам: левые концы (начала) отмечаете единичками в первой битовой карте, правые концы (концы) отмечаете единичками во второй битовой карте. То есть,не рисуете отрезки в битовых картах, а отмечаете факты начала или окончания. Теперь получение результата: цикл параллельно по обеим битовым картам и счетчик, увеличивающийся на единицу при наличии единички в первой битовой карте, и уменьшающийся на единицу при наличии единички во второй битовой карте. В тех местах, где счетчик становится больше нуля - начало результирующего отрезка, где становится равным нулю - конец. Меньше нуля счетчик не должен становиться, если все правильно, и все левые концы - это начала. Отработает меньше чем за секунду, если правильно организовать битовые карты так, чтоб по максимуму получить профит от SSE.
Блин, в вышеприведенном есть баг, если начала или концы нескольких отрезков совпадают. Облом. Хотя, надо подумать, может можно как-то обойти...
Придумал. Не две битовых карты, а одна парнобитовая. Каждому числу соответсвует пара бит в карте. 00 - ничего нет 01 - начало отрезка 10 - конец отрезка 11 - исключительная ситуация, на данной координате больше чем один конец/начало, для более подробного числа начал/концов на данной координате смотреть таблицу исключительных ситуаций (массив/список/хэш, выбрать, что лучше). Идеальность правда теряется, при желании можно задать входные данные так, что все выльется на исключительные ситуации. Но с деревом неидеальность еще хуже.
это понятно. нужно искать элемент и в цикле проверять пересечания. Dmitry_Milk, не самый лучший вариант. с деревьями, всё-таки, эффективней.
srm, а задача академическая или практическая? Если практическая, то может быть возможно перенести упорядочивание отрезков на этап возникновения этих данных в цифровом виде (ну, скажем, человек их вводит, или какие-то датчики неспешно генерируют). Тогда также можно не заморачиваться с деревьями, а просто обойтись обычным однонаправленным связным списком, вставляя в список новые отрезки в порядке их начал.
Практическая. Поэтому и не хочу использовать неэффективные алгоритмы. кусков может быть очень много (~10000, может больше). А упорядочивание - операция слишком накладная для списка такой длины. Да и вставка в упорядоченный список будет иметь сложность ~n.
