c ++ разреженный вектор
Вопрос 1)
У меня большой разреженный вектор парных чисел в c ++, мне нужно эффективно разобрать индексы ненулевых элементов из вектора. Очевидно, я могу перебрать всю длину и сделать это, есть ли лучший способ сделать это?
Решение
Если вы не обладаете какими-то особыми знаниями о структуре вектора двойных чисел (например, он отсортирован), цикл по всей его полноте является наиболее эффективным из тех, что вы получите.
Конечно, изменение структуры, предложенное эладиданом, вероятно, следует учитывать.
Другие решения
У меня большой разреженный вектор парных чисел в c ++, мне нужно эффективно разобрать индексы ненулевых элементов из вектора. Очевидно, я могу перебрать всю длину и сделать это, есть ли лучший способ сделать это?
Если вектор действительно редкий (n = o(N) где n это число ненулевых элементов и N размер вектора), затем представляет его в std::map<int,double> или же std::unordered_map<int,double> наверное лучше. С std::mapкак вы можете найти элемент в O(log(n)) , С std::unordered_map операция поиска занимает амортизированное время O(1), В обоих случаях количество ненулевых элементов — это просто размер контейнера. Оба подхода также принимают O(n) пространство вместо O(N),
Если ты не можешь изменить представление ваших данных, Вы должны изучить каждый элемент, чтобы отфильтровать те, которые почти равный в ноль. Тем не менее, эта задача смущающе параллельно, так что, возможно, вы можете разделить рабочую нагрузку на несколько потоков, чтобы хотя бы улучшить время выполнения (хотя и не сложность).