Алгоритм для уникальных краев находки от сетки полигона
Используйте std :: unordered_map < std :: string, int> . Обратите внимание, что std :: unordered_map < char, int> будет более эффективным, если требуется только один символ. std :: string позволяет подсчитывать сложные строки (например, map ["substring"] ++)
К картам можно обращаться, используя скобочные обозначения (например, map [index]), и, таким образом, можно эффективно устранить необходимость использования операторов if .
#include
#include
#include
int main()
{
std::unordered_map< std::string, int > map = { {"a",0} };
map["a"] += 1;
std::cout << map["a"];
}
3 ответа
Да
Используйте двойную карту хеша.
Каждый край имеет два индекса A, B. позволяет, говорит это A> B.
Первые высокоуровневые карты A карты хеша к другой карте хеша, которая является в свою очередь картами B к некоторому значению, которое представляет информацию, которую Вы хотите о каждом крае. (или просто bool, если Вы не должны хранить информацию для краев).
По существу это создает два дерева уровня, состоявшие из карт хеша.
Для поиска края в этой структуре, Вы берете больший индекс, ищете его на верхнем уровне и заканчиваете с картой хеша. затем возьмите меньший индекс и ищите его в этой второй карте хеша.
Просто для уточнения Вы хотите для списка полигона как это:
A +-----+ B
\ |\
\ 1 | \
\ | \
\ | 2 \
\| \
C +-----+ D
Затем вместо краев как это:
A - B -+
B - C +- first polygon
C - A -+
B - D -+
D - C +- second polygon
C - B -+
затем Вы хотите удалить дубликат B - C по сравнению с C - B край и совместно использовать его?
Какую проблему производительности Вы видите со своим алгоритмом? Я сказал бы, что набор, который имеет разумную реализацию хеша, должен работать довольно хорошо. С другой стороны, если Ваш хеш не будет оптимален для данных, то у Вас будет много коллизий, которые могли бы влиять на производительность плохо.
Вы оба корректны. Используя хороший hashset получил производительность далеко за пределами необходимых уровней. Я закончил тем, что прокрутил свой собственный небольшой набор хеша.
Общее количество краев будет между N/2 и N. N быть количеством уникальных вершин в сетке. Все общие края будут N/2, и все уникальные края будут N. Оттуда я выделяю буфер uint64 и упаковываю мои индексы в эти значения. Используя маленький набор уникальных таблиц я могу найти уникальные края быстро!