Раздельный перебор массива

[Himmelin]

Недавно столкнулся с задачей выборки одинаковых значений из массива с большим количеством элементов (больше тысячи). Задача была перебрать массив (например, ["green", "yellow", "blue", "green", "purple", "green"]) с помощью map и достать из него все green. Но через map довольно медленно. Есть какие-то более быстрые способы? Я слышал про какой-то метод располовинивания массива с большим количеством элементов, но гугл про это ничего толком не выдал

[voraa]

с помощью map

С помощью функции map? А при чем тут она при поиске? Есть функция .filter

с большим количеством элементов (больше тысячи).

Задачи конечно разные бывают, но на мой взгляд десятки тысяч это фигня.

Я слышал про какой-то метод располовинивания массива

Ну есть метод поиска делением пополам, но он применяется к отсортированным массивам.

[Himmelin]

Есть какая-нибудь ссылка на статью про метод деления пополам?

[Nexus]

Бенчмарк производительности методов перебора: https://jsben.ch/6S3sP (у меня всегда разный результат).

Ну есть метод поиска делением пополам, но он применяется к отсортированным массивам.

Вы про бинарный поиск? Он разве не неприменим в описанной выше задаче?

[Alexandroppolus]

Вы про бинарный поиск? Он разве не неприменим в описанной выше задаче?

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

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

[voraa]

Вы про бинарный поиск? Он разве не неприменим в описанной выше задаче?

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

Я не вижу тут отсортированного массива.

[Nexus]

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

И в чем его преимущество над обычным перебором?

Я возможно неправильно выразился. Применить то его можно, вот только смысл в этом какой?
У автора, насколько я понял, стоит задача максимально быстро найти в массиве все значения равные определенной строке. Разве бинарный поиск тут не будет медленнее, чем обычный перебор?

[Alexandroppolus]

Разве бинарный поиск тут не будет медленнее, чем обычный перебор?

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

Автор не уточнил эти моменты, к сожалению.

[voraa]

Разве бинарный поиск тут не будет медленнее, чем обычный перебор?

Если массив отсортирован, то конечно бинарный быстрее.
log2 (N) сравнений.
На 1000 элементов 10 сравнений.
А если неотсортирован, то ничего, кроме перебора не поможет.

А если многократно потребуется искать, то лучше сделать карту.

Отсортировать по возможности.

[Nexus]

Если массив большой и отсортированный

Если массив отсортирован

ТС привел пример массива. Он, судя по примеру, несортированный.
К тому же имеет, скорее всего, до двух тысяч элементов.