Как отобразить список KVP на Карта <Key, список <Value>> .. быстро

Question

Я быстро написал этот фрагмент кода, чтобы сделать работу

private void map() { 
    for (KVPair kvPair : content) { 
     String k = kvPair.getKey(); 
     String v = kvPair.getValue(); 

     if (mappedContent.containsKey(k)) { 
      List<String> values = mappedContent.get(k); 
      values.add(v); 
     } else { 
      List<String> values = new ArrayList<>(); 
      values.add(v); 
      mappedContent.put(k, values); 
     } 
    } 
} 

Он работает, и когда выбежала с 1k, 2k, 4k и 8k из случайные данные, я получаю следующую производительность (в среднем 100000 прогонов)

Running with 1,000 pairs 
    [perfRun] 100000 iterations took 3 seconds 
    [perfRun] Run time: 3758786000 ns. 1 iteration takes 37 us 
Running with 2,000 pairs 
    [perfRun] 100000 iterations took 6 seconds 
    [perfRun] Run time: 6675544000 ns. 1 iteration takes 66 us 
Running with 4,000 pairs 
    [perfRun] 100000 iterations took 13 seconds 
    [perfRun] Run time: 13337145000 ns. 1 iteration takes 133 us 
Running with 8,000 pairs 
    [perfRun] 100000 iterations took 27 seconds 
    [perfRun] Run time: 27109480000 ns. 1 iteration takes 271 us 

Грубо говоря, когда размер удваивается, время удваивается. Я бы взял линейный рост, но еще не удивился, можем ли мы сделать лучше? Можно ли сопоставлять вещи с использованием постоянного времени?

Answer 1

на основе @ ответ Quoi, то просто не знаю точно, если это имеет значение, чтобы сохранить блок еще после проверки нулевой

for (KVPair kvPair : content) { 
    String k = kvPair.getKey(); 
    List<String> values = mappedContent.get(k); 
    if (values == null) { 
     values = new ArrayList<>(); 
     mappedContent.put(k, values); 
    } 
    values.add(kvPair.getValue()); 
} 

также вы можете сделать некоторые предположения о том, как большой список может стать, поэтому вы передаете этот размер конструктору списка и сохраняете время, необходимое для переименования списка. Если память не является проблемой, вы можете принять content.size() + 1 как размер для списка.

Answer 2

Что я могу видеть, mappedContent.containsKey(k) его ненужным, грубо берет BigO(n), Вы можете избежать путем null проверки,

for (KVPair kvPair : content) { 
     String k = kvPair.getKey(); 
     String v = kvPair.getValue(); 
     List<String> values = mappedContent.get(k); 
     if (values!=null) { 
      values.add(v); 
     } else { 
      values = new ArrayList<>(); 
      values.add(v); 
      mappedContent.put(k, values); 
     } 
} 

Answer 3

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

Рассмотрите это: у вас есть список с n уникальных записей. Чтобы сопоставить каждый, к которому нужно получить доступ. Предположим, что затраты на доступ 1. Тогда необходимо n доступа. Таким образом, у вас есть сложность на n * 1 = n или линейное время, на которое указывает ваш бенчмаркинг.

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