Как может я увеличивать производительность в поиске карты с ключевым станд. типа:: строка?

Могу поспорить, что вы не пробовали то, что я предложил в комментариях: chapter.chapter_name for chapter in register.bloodbankchapters track by chapter._id приведет вас к тому, что в вашей модели появятся оба значения:

angular.module('selectExample', [])
  .controller('ExampleController', ['$scope', function($scope) {
    $scope.register = {
      regData: {
        branch: {},
      },
      bloodbankchapters: [
        {_id:'5c014c999cc48c3b0057988b', chapter_name:"AB"},
        {_id:'5c014c999cc48c3b0057988c', chapter_name:"A"},
      ],
    };
  }]);
<script src="https://cdnjs.cloudflare.com/ajax/libs/angular.js/1.7.5/angular.min.js"></script>
<div ng-app="selectExample" ng-controller="ExampleController">
  <select ng-model="register.regData.branch" ng-options ="chapter.chapter_name for chapter in register.bloodbankchapters track by chapter._id">
    <option ng-repeat="chapter in register.bloodbankchapters" >{{chapter.chapter_name}}</option>
  </select>
  <div>{{register.regData.branch}}</div>
</div>
[ 117]

9
задан Deduplicator 12 October 2018 в 00:18
поделиться

14 ответов

Во-первых, выключите все профилирование и ОТЛАДЬТЕ переключатели. Они могут замедлить STL очень.

Если это не это, часть проблемы может быть то, что Ваши строки идентичны для первых 80-90% строки. Это не плохо для карты, обязательно, но это для сравнений строк. Если это верно, Ваш поиск может взять намного дольше.

Например, в этом коде находят (), вероятно, приведет к нескольким строкам, выдерживает сравнение, но каждый возвратится после сравнения первого символа до "david", и затем первые три символа будут проверены. Так самое большее 5 символов будут проверены на вызов.

map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;

map<string,int>::iterator iter = names.find("daniel");

С другой стороны, в следующем коде, найдите (), вероятно, проверит 135 + символы:

map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;

map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");

Поэтому сравнения строк должны искать глубже для нахождения соответствия, так как начало каждой строки является тем же.

Используя размер () в Вашем сравнении для равенства не поможет Вам очень здесь, так как Ваш набор данных является настолько небольшим. Станд.:: карта сохранена отсортированной, таким образом, ее элементы могут искаться с двоичным поиском. Каждый вызов для нахождения должен привести меньше чем к 5 сравнениям строк для мисс и в среднем 2 сравнениям для хита. Но это действительно зависит от Ваших данных. Если большинство Ваших строк пути имеет различные длины, то проверка размера как Motti описывает, мог помочь много.

Что-то для рассмотрения при размышлении об альтернативных алгоритмах - то, сколько многих "хитов" Вы получаете. Является большая часть Вашей находки () вызовами, возвращая конец () или хит? Если большая часть Вашей находки () s возвращает конец () (промахи) затем, Вы ищете всю карту каждый раз, когда (2logn, строка выдерживает сравнение).

Hash_map является хорошей идеей; это должно включить Ваше время поиска приблизительно половина для хитов; больше для промахов.

Пользовательский алгоритм может требоваться из-за природы строк пути, особенно если Ваш набор данных имеет общую родословную как в вышеупомянутом коде.

Другая вещь рассмотреть состоит в том, как Вы получаете свои строки поиска. При многократном использовании их это может помочь закодировать их во что-то, что легче сравнить. Если Вы используете их однажды и отбрасываете их, то этот шаг кодирования является, вероятно, слишком дорогим.

Я использовал что-то как дерево Кодирования методом Хаффмана однажды (давным-давно) для оптимизации поисков строки. Дерево поиска двоичной строки как этот может быть более эффективным в некоторых случаях, но его довольно дорогое для маленьких наборов как Ваши.

Наконец, изучите альтернативный станд.:: реализации Map. Я услышал плохие вещи о части stl производительности кода VC. Библиотека DEBUG в особенности плоха о проверке Вас на каждом вызове. StlPort раньше был хорошей альтернативой, но я не попробовал его через несколько лет. Я всегда любил Повышение также.

14
ответ дан 4 December 2019 в 06:02
поделиться

hash_map не является стандартным, попытайтесь использовать unordered_map доступный в tr1 (который доступен в повышении, если Ваш набор инструментальных средств уже не имеет его).

Для небольших чисел строк Вы могли бы лучше использовать vector, как map обычно реализуется как дерево.

0
ответ дан 4 December 2019 в 06:02
поделиться

Станд. попытки:: tr1:: unordered_map (найденный в заголовке <tr1/unordered_map>). Это - карта хеша, и, в то время как она не поддерживает отсортированный порядок элементов, вероятно, будет намного быстрее, чем обычная карта.

Если Ваш компилятор не поддерживает TR1, получает более новую версию. MSVC и gcc и поддерживают TR1, и я полагаю, что новейшие версии большинства других компиляторов также имеют поддержку. К сожалению, много сайтов справочного руководства по библиотеке не было обновлено, таким образом, TR1 остается в основном неизвестной частью технологии.

Я надеюсь, что C++ 0x не является тем же путем.

Править: Обратите внимание что метод хеширования значения по умолчанию tr1:: unordered_map является tr1:: хеш, который должен быть специализирован для работы над UDT, вероятно.

1
ответ дан 4 December 2019 в 06:02
поделиться

Где у Вас есть длинные общие подстроки, trie мог бы быть лучшей структурой данных, чем карта или hash_map. Я сказал, "мог бы", хотя - hash_map уже только пересекает ключ однажды на поиск, быть довольно быстрым - также. Я не буду обсуждать это далее, так как другие уже имеют.

Вы могли также рассмотреть косое дерево, если некоторые ключи более часто ищутся, чем другие, но конечно это делает поиск худшего случая хуже, чем сбалансированное дерево, и поиски видоизменяют операции, которые могут иметь значение для Вас, если Вы используете, например, блокировка читателя-устройства записи.

При заботе о выполнении поисков о больше, чем модификации Вы могли бы добиться большего успеха с деревом AVL, чем красно-черное, которое я думаю, то, что реализации STL обычно используют для карты. Дерево AVL обычно лучше балансируется и так в среднем потребует меньшего количества сравнений на поиск, но различие является крайним.

Нахождение реализации их, что Вы довольны, могло бы быть проблемой. Поиск на Повышении, основная страница предлагает, чтобы у них были откос и дерево AVL, но не trie.

Вы упомянули в комментарии, что у Вас никогда нет поиска, которому не удается найти что-либо. Таким образом, Вы могли в теории пропускать заключительное сравнение, которое в дереве 15 <2^4 элементы могли дать Вам что-то как 20-25%-е ускорение, не делая ничего больше. На самом деле, возможно, больше, чем это, так как равные строки являются самыми медленными для сравнения. Стоит ли записать, что Ваш собственный контейнер только для этой оптимизации является другим вопросом.

Вы могли бы также рассмотреть местность ссылки - я не знаю, могли ли Вы избежать случайной страницы мисс путем выделения ключей и узлов из маленькой "кучи". Если Вам только нужны приблизительно 15 записей за один раз, то, принимая предел имени файла ниже 256 байтов Вы могли удостовериться, что все получило доступ во время поиска, вписывается в единственную 4k страницу (кроме искавшего ключа, конечно). Может случиться так, что сравнение строк незначительно по сравнению с загрузками на несколько страниц. Однако, если бы это - Ваше узкое место должно быть огромное количество продолжения поисков, таким образом, я предположил бы, что все обоснованно близко к ЦП. Стоящий проверки, возможно.

Другая мысль: при использовании пессимистической блокировки на структуре, где существует много конкуренции (Вы сказали в комментарии, программа является в широком масштабе многопоточной), затем независимо от того, что профилировщик говорит Вам (что кодирует циклы ЦП, потрачены в), это могло бы стоить Вам больше, чем Вы думаете путем эффективного ограничения Вас 1 ядром. Попробовать блокировку читателя-устройства записи?

1
ответ дан 4 December 2019 в 06:02
поделиться

Возможно, Вы могли инвертировать строки до использования их как ключи в карте? Это могло помочь, если первые несколько букв каждой строки идентичны.

2
ответ дан 4 December 2019 в 06:02
поделиться

В зависимости от случаев использования существуют некоторые другие методы, которые можно использовать. Например, у нас было приложение, которое должно было не отставать от более чем миллиона различных путей к файлам. Проблемой с этим там были тысячи объектов, которые должны были сохранить маленькие карты этих путей к файлам.

Начиная с добавления новых путей к файлам к набору данных была нечастая операция, когда путь был добавлен к системе, основная карта искалась. Если путь не был найден, то он был добавлен, и было возвращено новое упорядоченное целое число (запускающийся в 1). Если путь уже существовал, то ранее присвоенное целое число было возвращено. Затем каждая карта, сохраняемая каждым объектом, была преобразована от основанной на строке карты до целочисленной карты. Мало того, что это значительно улучшало производительность, она уменьшила использование памяти, не имея столько дубликатов строк.

Несомненно, это - очень определенная оптимизация. Но когда дело доходит до повышений производительности, Вы часто имеете необходимость для создания специализированных решений к определенным проблемам.

И я ненавижу строки :) Не, они замедляются для сравнения, но они могут действительно повредить кэши ЦП на высокопроизводительном программном обеспечении.

1
ответ дан 4 December 2019 в 06:02
поделиться

Вот некоторые вещи, которые можно рассмотреть:

0) Вы уверены, что это - то, где узкое место производительности? Как результаты Определяют количество, Cachegrind, gprof или что-то как этот? Поскольку поиски на такой карте SMAP должны быть довольно быстрыми...

1) Можно переопределить функтор, используемый для сравнения ключей в станд.:: карта <>, существует второй шаблонный параметр, чтобы сделать это. Я сомневаюсь, что можно сделать намного лучше, чем оператор <как бы то ни было.

2) Содержание карты изменяющийся много? В противном случае и, учитывая очень небольшой размер Вашей карты, возможно, с помощью отсортированного векторного и двоичного поиска мог привести к лучшим результатам (например, потому что можно использовать местность памяти лучше.

3) Элементы известны во время компиляции? Вы могли использовать идеальную хеш-функцию для улучшения времен поиска, если это так. Поиск gperf в сети.

4) У Вас есть много поисков, которым не удается найти что-нибудь? Если так, возможно, сравнение с первыми и последними элементами в наборе может устранить много несоответствий, более быстрых, чем полный поиск каждый раз.

Они уже были предложены, но более подробно:

5) Так как у Вас есть так мало строк, возможно, Вы могли использовать другой ключ. Например, являются всеми одинаковыми Ваши ключи размер? Можно ли использовать класс, содержащий массив фиксированной длины символов? Можно ли преобразовать строки в числа или некоторую структуру данных только с числами?

1
ответ дан 4 December 2019 в 06:02
поделиться

У Motti есть хорошее решение. Однако я вполне уверен, что для Вашего <15 элементов карта не является правильным путем, потому что его издержки всегда будут больше, чем та из простой справочной таблицы с соответствующей схемой хеширования. В Вашем случае могло бы даже быть достаточно хешировать одной только длиной, и если это все еще производит коллизии, используйте линейный поиск посредством всех записей той же длины.

Чтобы установить, если я прав, сравнительный тест, конечно, требуется, но я совершенно уверен в его результате.

3
ответ дан 4 December 2019 в 06:02
поделиться

станд.:: компаратор карты не является станд.:: equal_to это - станд.:: меньше, я не уверен, что лучший способ сорвать <сравнивают так, чтобы это было бы быстрее, чем созданный в одном.

Если всегда существует <15 elems, возможно, Вы могли бы использовать ключ помимо станд.:: строка?

3
ответ дан 4 December 2019 в 06:02
поделиться

Первая вещь состоит в том, чтобы попытаться использовать hash_map, если это возможно - Вы правы, что стандартная строка выдерживает сравнение, сначала не проверяет на размер (так как это выдерживает сравнение лексикографически), но написание Вашего собственного кода карты является чем-то, что Вы были бы более обеспеченным предотвращением. От Вашего вопроса это кажется, что Вы не должны выполнять итерации по диапазонам; в этом случае карта не имеет ничего, что hash_map не делает.

Это также зависит от того, какие ключи Вы имеете в своей карте. Они обычно очень долго? Также, что "немного замедляется" средний? Если Вы не представили код, довольно возможно, что это - занимающая время другая часть.

Обновление: Хм, узкое место в Вашей программе является картой:: найдите, но карта всегда имеет меньше чем 15 элементов. Это заставляет меня подозревать, что профиль так или иначе вводил в заблуждение, потому что находка на карте это маленькое не должно быть медленно, вообще. На самом деле, карта:: находка должна быть настолько быстрой, просто издержки профилирования могли быть больше, чем сам вызов находки. Я должен спросить снова, действительно ли Вы уверены, что это - действительно узкое место в Вашей программе? Вы говорите, что строки являются путями, но Вы не делаете никакого вида вызовов ОС, доступа к файловой системе, доступа к диску в этом цикле? Любой из тех должен быть порядками величины медленнее, чем карта:: найдите на маленькой карте. Действительно любой способ получить строку должен быть медленнее, чем карта:: найти.

5
ответ дан 4 December 2019 в 06:02
поделиться

Можно попытаться использовать отсортированный вектор (вот один образец), это может оказаться быстрее (необходимо будет представить его для проверки, конечно).

Причины думать это будет быстрее:

  1. Меньше выделений памяти и освобождения (вектор расширится до максимального используемого размера и затем повторное использование, освободили память).
  2. Двоичная находка с произвольным доступом должна быть быстрее, чем обход дерева (особенно из-за местности данных).

Причины думать это будет медленнее:

  1. Deleations и дополнения будут означать перемещать строки в памяти с тех пор string swap эффективно, и размер набора данных является небольшим, это не может быть проблемой.
4
ответ дан 4 December 2019 в 06:02
поделиться

Вы могли бы рассмотреть предварительные вычисления хеша для строки и сохранения это в Вашей карте. Выполнение так дает преимущество хеша, выдерживает сравнение вместо строки, выдерживает сравнение во время поиска через станд.:: дерево карты.

class HashedString
{
  unsigned m_hash;
  std::string m_string;

public:
  HashedString(const std::string& str)
    : m_hash(HashString(str))
    , m_string(str)
  {};
  // ... copy constructor and etc...

  unsigned GetHash() const {return m_hash;}
  const std::string& GetString() const {return m_string;}
};

Это обладает преимуществами вычислений хеша строки однажды на конструкции. После этого Вы могли реализовать функцию сравнения:

struct comp
{
  bool operator()(const HashedString& lhs, const HashedString& rhs)
  {
    if(lhs.GetHash() < rhs.GetHash()) return true;
    if(lhs.GetHash() > rhs.GetHash()) return false;
    return lhs.GetString() < rhs.GetString();
  }
};

Так как хеши теперь вычисляются на HashedString конструкция, они хранятся тот путь в станд.:: карта, и таким образом, сравнивание может произойти очень быстро (целое число выдерживают сравнение) в астрономически высоком проценте времени, возвращаясь к стандартной строке выдерживает сравнение, когда хеши равны.

2
ответ дан 4 December 2019 в 06:02
поделиться

Как Даже сказано оператор, используемый в a set < нет ==.

Если Вы не заботитесь о порядке строк в Вашем set можно передать set пользовательский компаратор, который работает лучше, чем постоянный клиент меньше.

Например, если много Ваших строк имеет подобные префиксы (но они варьируются по длине), можно отсортировать по длине строки (так как string.length постоянная скорость).

Если Вы действительно так остерегаетесь частой ошибки:

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() < rhs.length())
            return true;
        return lhs < rhs;
    }
};

Этот оператор не поддерживает строгое слабое упорядочивание, у Вас может быть две строки, которые являются каждым меньше, чем другой.

string a = "z";
string b = "aa";

Следуйте за логикой, и Вы будете видеть это comp(a, b) == true и comp(b, a) == true.

Корректная реализация:

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() != rhs.length())
            return lhs.length() < rhs.length();
        return lhs < rhs;
    }
};
13
ответ дан 4 December 2019 в 06:02
поделиться

Почему бы вам не использовать вместо этого хеш-таблицу? boost :: unordered_map может. Или вы можете развернуть собственное решение и сохранить crc строки вместо самой строки. Или еще лучше, поместите #defines для строк и используйте их для поиска, например,

#define "STRING_1" STRING_1
0
ответ дан 4 December 2019 в 06:02
поделиться
Другие вопросы по тегам:

Похожие вопросы: