Шпаргалка Java програміста 7.2 Типові завдання: Обхід Map'и, підрахунок кількості входжень підрядка

image
У мене є хобі: я збираю різні рішення типових завдань в Java, які знаходжу в інеті, і намагаюся вибрати найбільш оптимальний за розміром/продуктивності/елегантності. В першу чергу по продуктивності. Давайте розглянемо таку типові задачі, які часто зустрічаються в програмування на Java як "обхід Map'и" і підрахунок кількості входжень рядків, різні варіанти їх рішень (включаючи "красиві" і не дуже) та їх продуктивність.
Англійські версії можна знайти на Stackoverflow: з обходу map's, за підрахунком входжень підрядків.
Так само раджу подивитися мій opensource проект useful-java-links — можливо, найбільш повна колекція корисних бібліотек Java та фреймворків.
Загальний зміст 'Шпаргалок'1. JPA і Hibernate в питаннях і відповідях
2. Триста п'ятдесят найпопулярніших не мобільних Java opensource проектів на github
3. Колекції в Java (стандартні, guava, apache, скарб, gs-collections та інші)
4. Java Stream API
5. Двісті п'ятдесят російськомовних навчальних відео доповідей і лекцій про Java
6. Список корисних посилань для Java програміста
7 Типові завдання
  7.1 Оптимальний шлях перетворення InputStream в рядок
  7.2 найпродуктивніший спосіб обходу Map'и, підрахунок кількості входжень підрядка
1. Обхід Map's
Отже, якщо пошукати в інтернеті знайдеться з десяток різних способів виконати обхід map'и в загальному випадку, коли нам важливі і ключі і значення (природно, обхід просто ключів або значень робиться елементарно). Частина з них відрізняється лише синтаксичним цукром, частина принципово різні. Насправді, звичайно, які рішення повільні і які швидкі давно відомо, але все-таки цікаво скільки у нас вийде у папуг.
Для повноти картини розглянемо не тільки обхід звичайних Map, але і їх аналогів з IterableMap
Apache Collections
та MutableMap of
Eclipse (CS) collections
.
Давайте подивимося на варіанти:
Умови задачі, нехай у нас буде Map'а чисел, будемо шукати суму всіх ключів і значень в цій Map'и. Така задача з одного боку максимально спрощена, з іншого гарантує нам що оптимізатор Java не зможе викинути частину коду.
  1. Використовуючи iterator, Map.Entry і цикл while. Не самий гарний варіант, по суті аналог варіанту (2), але подивимося наскільки вони відрізняються.
    long i = 0;
    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
    while (it.hasNext()) {
    Map.Entry<Integer, Integer> pair = it.next();
    i += pair.getKey() + pair.getValue();
    }

  2. Використовуючи Map.Entry і цикл foreach. Класичний варіант обходу map'и.
    long i = 0;
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
    i += pair.getKey() + pair.getValue();
    }

  3. Використовуючи foreach
    Java 8
    . Подивимося наскільки продуктивний новий спосіб, який з'явився в Java 8.
    final long[] i = {0};
    map.forEach((k, v) -> i[0] += k + v);

  4. Використовуючи keySet і foreach. Вважається, що цей спосіб дуже повільний, питання тільки на скільки.
    long i = 0;
    for (Integer key map.keySet()) {
    i += key + map.get(key);
    }

  5. Використовуючи keySet і iterator. По суті, варіант 4 тільки без синтаксичного цукру.
    long i = 0;
    Iterator<Integer> itr2 = map.keySet().iterator();
    while (itr2.hasNext()) {
    Integer key = itr2.next();
    i += key + map.get(key);
    }

  6. Використовуючи for і Map.Entry. Аналог 1 і 2, тільки в "старому стилі"
    long i = 0;
    for (Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); entries.hasNext(); ) {
    Map.Entry<Integer, Integer> entry = entries.next();
    i += entry.getKey() + entry.getValue();
    }

  7. Використовуючи
    Java 8
    та Stream Api
    final long[] i = {0};
    map.entrySet().stream().forEach(e -> i[0] += e.getKey() + e.getValue());

  8. Використовуючи
    Java 8
    і паралельний Stream Api
    final long[] i = {0};
    map.entrySet().stream().parallel().forEach(e -> i[0] += e.getKey() + e.getValue());

  9. Використовуючи IterableMap
    Apache Collections
    . Дана map'a відрізняється незвичайним способом обходу.
    long i = 0;
    MapIterator<Integer, Integer> it = iterableMap.mapIterator();
    while (it.hasNext()) {
    i += it.next() + it.getValue();
    }

  10. Використовуючи MutableMap
    Eclipse collections
    (колишні GS колекції). Дана map'a отримала свій forEach метод набагато раніше, ніж з'явилася Java 8.
    final long[] i = {0};
    mutableMap.forEachKeyValue((key, value) -> {
    i[0] += key + value;
    });

Тести продуктивності
Типове попередження: Всі результати подано як є, виміри продуктивності річ складна, у вашій системі всі числа можуть бути зовсім інші, тому не варто мені вірити, вихідні коди на github'eзавжди можна отримати результати самостійно. Якщо вважаєте, що я десь помилився при вимірах продуктивності (а це завжди можливо), буду вдячний якщо напишіть в лічку або коментарі.
Режим = середній час (AverageTime), система = Win 8.1 64-bit, Intel i7-4790 3.60 GHz 3.60 GHz, 16 GB, чим менше score тим краще)
1) Для невеликих map (100 елементів), score 0.312 — найкраще значення
Benchmark Size Mode Cnt Score Error Units
3. ForEachAndJava8 100 avgt 100 0.312 ± 0.003 us/op
10. EclipseMap 100 avgt 100 0.354 ± 0.003 us/op
2. ForEachAndMapEntry 100 avgt 100 0.403 ± 0.005 us/op
1. WhileAndMapEntry 100 avgt 100 0.427 ± 0.006 us/op
6. ForAndIterator 100 avgt 100 0.427 ± 0.006 us/op
7. Java8StreamApi 100 avgt 100 0.529 ± 0.004 us/op
9. ApacheIterableMap 100 avgt 100 0.585 ± 0.008 us/op
4. KeySetAndForEach 100 avgt 100 0.937 ± 0.011 us/op
5. KeySetAndIterator 100 avgt 100 0.94 ± 0.011 us/op
8. Java8StreamApiParallel 100 avgt 100 6.066 ± 0.051 us/op

2) Для середніх map з 10000 елементами, score 35.301 — найкраще значення
Benchmark Size Mode Cnt Score Error Units
10. EclipseMap 10000 avgt 100 35.301 ± 0.697 us/op
3. ForEachAndJava8 10000 avgt 100 39.797 ± 0.309 usd/op
2. ForEachAndMapEntry 10000 avgt 100 43.149 ± 0.313 usd/op
1. WhileAndMapEntry 10000 avgt 100 43.295 ± 0.314 us/op
6. ForAndIterator 10000 avgt 100 44.009 ± 0.379 us/op
7. Java8StreamApi 10000 avgt 100 49.378 ± 0.415 usd/op
5. KeySetAndIterator 10000 avgt 100 97.844 ± 0.896 us/op
4. KeySetAndForEach 10000 avgt 100 99.317 ± 0.862 us/op
8. Java8StreamApiParallel 10000 avgt 100 112.364 ± 0.167 us/op
9. ApacheIterableMap 10000 avgt 100 138.379 ± 1.387 us/op

3) Для map з 30000 елементами, score 122.277 — найкраще значення
Benchmark Size Mode Cnt Score Error Units
10. EclipseMap 30000 avgt 100 122.277 ± 3.896 us/op
3. ForEachAndJava8 30000 avgt 100 136.906 ± 2.392 us/op
2. ForEachAndMapEntry 30000 avgt 100 145.845 ± 1.895 us/op
1. WhileAndMapEntry 30000 avgt 100 149.186 ± 2.621 us/op
6. ForAndIterator 30000 avgt 100 149.353 ± 2.427 us/op
7. Java8StreamApi 30000 avgt 100 181.114 ± 3.272 us/op
8. Java8StreamApiParallel 30000 avgt 100 342.546 ± 1.206 usd/op
5. KeySetAndIterator 30000 avgt 100 350.564 ± 8.662 us/op
4. KeySetAndForEach 30000 avgt 100 364.362 ± 9.416 us/op
9. ApacheIterableMap 30000 avgt 100 536.749 ± 25.819 us/op

Графік (тести в залежності від розміру map'и)
enter image description here
Таблиця (тести в залежності від розміру map'и)
Benchmark 100 500 900 1300 1700 2100 2500
10. EclipseMap 0.354 1.384 3.816 3.304 6.68 7.427 8.712
3. ForEachAndJava8 0.312 1.692 3.143 4.265 6.506 8.343 9.821
6. ForAndIterator 0.427 2.089 3.746 4.776 7.407 9.091 10.753
2. ForEachAndMapEntry 0.403 2.536 3.951 5.028 7.503 9.211 10.918
1. WhileAndMapEntry 0.427 2.026 3.4815 4.937 7.511 9.217 12.22
7. Java8StreamApi 0.529 2.343 4.264 5.399 8.826 12.633 12.918
9. ApacheIterableMap 0.585 2.725 5.574 9.292 13.01 17.719 23.882
5. KeySetAndIterator 0.94 4.592 8.24 12.496 16.077 21.012 24.389
4. KeySetAndForEach 0.937 4.572 8.251 12.522 14.831 20.502 24.881
8. Java8StreamApiParallel 6.066 12.152 16.563 18.512 25.987 28.813 33.336

Всі тести на github
Попередження:
1) Обхід HashMap, EclipseMap і ApacheIterableMap розглядався тільки для типового випадку коли колізій немає або майже немає, у разі коли колізій багато — результати можуть бути зовсім іншими. Так само не розглянуті випадки додавання елементів, випадкового доступу і т. п., тобто тільки з цього тесту не можна судити яка map'a швидше і краще в цілому,
2) Варіант з Java8StreamApiParallel насправді не зовсім коректний, оскільки сума збільшується різними тредами без синхронізації, але я намагався поміряти саме швидкість обходу елементів (наприклад, у разі зміни поля кожного класу в map'e), сума потрібна була тільки для виключення спроб оптимізації компілятором.
2. Підрахунок кількість входжень підрядка в рядок
Отже візьмемо наступний підрядок і знайдемо всі точки в ній:
String testString = "a.b.c.d";

Хотів відразу попередити: я взяв для тестування всі варіанти, запропоновані в темі StackOverflow, здоровий глузд підказує, що частина з них далеко не оптимальне забивання цвяхів улюбленим мікроскопом, але мені було просто цікаво що вийде в кожному випадку. Тому, враховуйте, що далеко не всі варіанти нижче варто використовувати в реальному додатку!
1) Використовуючи Apache Commons
int apache = StringUtils.countMatches(testString, ".");
System.out.println("apache = " + apache);

2) Використовуючи Spring Framework's
int spring = org.springframework.util.StringUtils.countOccurrencesOf(testString, ".");
System.out.println("spring = " + spring);

3) Використовуючи replace
int replace = testString.length() - testString.replace(".", "").length();
System.out.println("replace = " + replace);

4) Використовуючи replaceAll (case 1)
int replaceAll = testString.replaceAll("[^.]", "").length();
System.out.println("replaceAll = " + replaceAll);

5) Використовуючи replaceAll (case 2)
int replaceAllCase2 = testString.length() - testString.replaceAll("\\.", "").length();
System.out.println("replaceAll (second case) = " + replaceAllCase2);

6) Використовуючи split
int split = testString.split("\\.",-1).length-1;
System.out.println("split = " + split);

7) Використовуючи Java8 (case 1)
long java8 = testString.chars().filter(ch -> ch =='.').count();
System.out.println("java8 = " + java8);

8) Використовуючи Java8 (case 2), можливо дещо краще в разі unicode рядка ніж case 1
long java8Case2 = testString.codePoints().filter(ch -> ch =='.').count();
System.out.println("java8 (second case) = " + java8Case2);

9) Використовуючи StringTokenizer
int stringTokenizer = new StringTokenizer(" " +testString + " ", ".").countTokens()-1;
System.out.println("stringTokenizer = " + stringTokenizer);

Останній варіант, дещо некоректним, так як дві точки будуть вважатися за одну, тобто для a...b.c....d or ...a.b.c.d або a....b......c.....d… кілька точок будуть вважатися за одну.
Типове попередження: Всі результати подано як є, виміри продуктивності річ складна, у вашій системі всі числа можуть бути зовсім інші, тому не варто мені вірити, вихідні коди на github'eзавжди можна отримати результати самостійно. Якщо вважаєте, що я десь помилився при вимірах продуктивності (а це завжди можливо), буду вдячний якщо напишіть в лічку або коментарі.
Всі тести на github
Результати вимірів на короткій рядку (використовуючи JMH mode = AverageTime, значення
0.010
краще ніж
0.351
):
Benchmark Mode Cnt Score Error Units
1. countMatches avgt 5 0.010 ± 0.001 us/op
2. countOccurrencesOf avgt 5 0.010 ± 0.001 us/op
3. stringTokenizer avgt 5 0.028 ± 0.002 us/op
4. java8_1 avgt 5 0.077 ± 0.005 us/op
5. java8_2 avgt 5 0.078 ± 0.003 us/op
6. split avgt 5 0.137 ± 0.009 us/op
7. replaceAll_2 avgt 5 0.302 ± 0.047 us/op
8. replace avgt 5 0.303 ± 0.034 us/op
9. replaceAll_1 avgt 5 0.351 ± 0.045 us/op

Результати вимірів на довгому рядку довжиною в 2142 символів (використовуючи JMH mode = AverageTime, значення
0.010
краще ніж
0.351
):
Benchmark Mode Cnt Score Error Units
1. countMatches avgt 5 2.392 ± 0.172 us/op
2. countOccurrencesOf avgt 5 2.362 ± 0.060 us/op
3. stringTokenizer avgt 5 5.931 ± 0.112 us/op
4. java8 avgt 5 9.626 ± 0.463 usd/op
5. java8_1 avgt 5 8.586 ± 0.251 us/op
6. split avgt 5 21.201 ± 1.037 us/op
7. replaceAll2 avgt 5 26.614 ± 1.026 us/op
8. replaceAll1 avgt 5 31.505 ± 1.046 usd/op
9. replace avgt 5 33.462 ± 2.329 us/op

p.s. Англійські версії можна знайти на Stackoverflow: з обходу map's, за підрахунком входжень підрядків, вихідні коди в моєму проекті useful-java-links. Буду вдячний плюсів SO або github'e, якщо стаття сподобалася і вважаєте, що вони заслужені.
P. P. S. Так само раджу подивитися мій opensource проект useful-java-links — можливо, найбільш повна колекція корисних Java бібліотек, фреймворків та російськомовного навчального відео. Так само є аналогічна англійська версія цього проекту і починаю opensource підпроект Hello world з підготовки колекції простих прикладів для різних Java бібліотек в одному maven проекті (буду вдячний за будь-яку допомогу).
Загальний зміст 'Шпаргалок'1. JPA і Hibernate в питаннях і відповідях
2. Триста п'ятдесят найпопулярніших не мобільних Java opensource проектів на github
3. Колекції в Java (стандартні, guava, apache, скарб, gs-collections та інші)
4. Java Stream API
5. Двісті п'ятдесят російськомовних навчальних відео доповідей і лекцій про Java
6. Список корисних посилань для Java програміста
7 Типові завдання
  7.1 Оптимальний шлях перетворення InputStream в рядок
  7.2 найпродуктивніший спосіб обходу Map'и, підрахунок кількості входжень підрядка

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.