Раздельный перебор массива
Недавно столкнулся с задачей выборки одинаковых значений из массива с большим количеством элементов (больше тысячи). Задача была перебрать массив (например, ["green", "yellow", "blue", "green", "purple", "green"]) с помощью map и достать из него все green. Но через map довольно медленно. Есть какие-то более быстрые способы? Я слышал про какой-то метод располовинивания массива с большим количеством элементов, но гугл про это ничего толком не выдал :thanks:
|
Цитата:
Цитата:
Цитата:
|
Есть какая-нибудь ссылка на статью про метод деления пополам?
|
Бенчмарк производительности методов перебора: https://jsben.ch/6S3sP (у меня всегда разный результат).
Цитата:
|
Цитата:
Найти бинарным поиском первое попавшееся значение, потом от него пробежаться вправо и влево, пособирать все такие же. Если данная операция будет выполняться многократно, то имеет смысл на старте создать карту (значение -> массив) для всех значений. |
Цитата:
Цитата:
|
Цитата:
Я возможно неправильно выразился. Применить то его можно, вот только смысл в этом какой? У автора, насколько я понял, стоит задача максимально быстро найти в массиве все значения равные определенной строке. Разве бинарный поиск тут не будет медленнее, чем обычный перебор? |
Цитата:
Автор не уточнил эти моменты, к сожалению. |
Цитата:
log2 (N) сравнений. На 1000 элементов 10 сравнений. А если неотсортирован, то ничего, кроме перебора не поможет. Цитата:
|
Цитата:
Цитата:
К тому же имеет, скорее всего, до двух тысяч элементов. |
Цитата:
Я приводил пример - суммирование 10 000 000 элементов массива занимает 20 мс. https://javascript.ru/forum/530002-post6.html |
Цитата:
|
Цитата:
Правда, в его случае используется map, то есть лишние расходы, но тем не менее. |
Я даже не представляю, что там может быть долго?
Вот тест. 100 раз выполняется просмотр массива из 10 000 элементов для поиска одинаковых
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html; charset=utf-8" lang="ru">
<meta name="viewport" content="width=device-width, initial-scale=1.0" >
<title>TEST SPEED</title>
<style>
</style>
</head>
<body id="body" >
<script>
const r = (m) => Math.random()*m | 0;
const colors = ['red', 'orange', 'yellow', 'green', 'cyan', 'blue', 'violet'];
const ar = [];
const l = 10_000;
for (let i = 0; i < l; i++) ar.push ({color: colors[r(colors.length)], data: r(10)});
const nc = 100;
let findsame = (a, key) => {
const res = [];
for (let i=0; i<a.length; i++) {
if (key.color === a[i].color && key.data === a[i].data) res.push(i);
}
return res
}
const t0 = performance.now();
for (ic = 0; ic < nc; ic++) {
const key = {color: colors[r(colors.length)], data: r(10)};
const res = findsame(ar, key);
// console.log(ic, res);
}
const dt = (performance.now()-t0)/1000;
alert(` Time: ${dt} seconds`);
</script>
</body>
</html>
У меня получается 6-8 мс на ноуте (довольно мощный) и 50-60 мс на не слишком навороченном смартфоне. |
Цитата:
|
Цитата:
Ничего не помогает. Когда перехожу в режим редактирования там < стоит. Ну меняю < на <. Толку нет. Но ошибок не выдает и при раскомментаренном console.log(ic, res); результаты выдает, хотя время, конечно, другое. |
Нифига себе, происки империалистов, сейчас попробуем. )
var a = b < c;
const r = (m) => Math.random()*m | 0;
const colors = ['red', 'orange', 'yellow', 'green', 'cyan', 'blue', 'violet'];
const ar = [];
const l = 10_000;
for (let i = 0; i < l; i++) ar.push ({color: colors[r(colors.length)], data: r(10)});
const nc = 100;
let findsame = (a, key) => {
const res = [];
for (let i=0; i<a.length; i++) {
if (key.color === a[i].color && key.data === a[i].data) res.push(i);
}
return res
}
const t0 = performance.now();
for (ic = 0; ic < nc; ic++) {
const key = {color: colors[r(colors.length)], data: r(10)};
const res = findsame(ar, key);
// console.log(ic, res);
}
const dt = (performance.now()-t0)/1000;
alert(` Time: ${dt} seconds`);
Нет проблем, скопировал - текст в коде, заменил - все норма. У вас клавиша < на клавиатуре решила, что так лучше будет :) |
Цитата:
Да хрен с ней лишь бы работало. Цитата:
|
Цитата:
|
| Часовой пояс GMT +3, время: 22:15. |