За линейное время заменить каждый элемент list1 его номером в list2

@Etyuhibosecyu · Регистрация: 13.07.2017

Студворк — интернет-сервис помощи студентам

Например, list1: { 147, 256, 147, 333, 256, 168, 961, 256, 729, 961, 333 }; list2: { 147, 256, 333, 168, 961, 729 }. Выход: { 0, 1, 0, 2, 1, 3, 4, 1, 5, 4, 2 }. То есть каждый элемент выхода равен list2.IndexOf(list1[i]), но если так буквально и записать, время будет квадратичным. А может ли Linq сделать его линейным?

@Соколиный глаз · 24.03.2019, 17:49

Почему квадратичным? За одну операцию знамены номером оно будет линейным. Для оптимизации можно кешироваать пары "число - номер" в словарь и при каждой операции замены номером смотреть кеширована ли пара и если да, то брать номер из словаря иначе искать.

@Etyuhibosecyu · 24.03.2019, 17:51 **[ТС]**

А мне нужно, чтобы не за одну операцию, а общее время выполнения было линейным.

@Рядовой · 24.03.2019, 19:23

Сообщение от Etyuhibosecyu

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

а есть какие то вразумительные аргументы этому предположению?

Сообщение от Etyuhibosecyu

Linq сделать его линейным?

линк только увеличит время работы алгоритма

@alexus5 · 24.03.2019, 20:21

Etyuhibosecyu,
здесь приходит на ум пока только один трюк, который иногда может и не сработать)
а Linq будет лишь для красоты:

C#
1
2
3
4
5
6
7
        static List<int> NewList3(List<int> list1, List<int> list2)
        {
            var max = list2.Max();
            var exists = new int[max+1];
            for (int i = 0; i < list2.Count; i++) exists[list2[i]] = i;
            return list1.Select(x => exists[x]).ToList();
        }

@Etyuhibosecyu · 24.03.2019, 20:29 **[ТС]**

alexus5, такое для вас открытие Америки? Вчера никто не помог, а вы помогли, а сегодня?

C#
1
list1.Join(list2.Select((x, i) => (x, i)), x => x, y => y, (x, y) => y.i).ToList()

Прочитал пример на просторах Интернета и переделал под себя...

Добавлено через 2 минуты
Это решение работает, даже если списки имеют тип не int...

@Usaga · 25.03.2019, 07:46

Etyuhibosecyu, если последовательности малы (как на примере в первом посте), то IndexOf будет самым эффективным решением. Значительно эффективнее Linq или чего-то другого.

Не забывайте (или знайте), что Linq - пачка итераторов разной степени упоротости. Эти итераторы - классы, объекты которых нужно создать, методы которых нужно вызывать. Потом её и мусор для GC будет. Шесть раз пробежаться по маленькому массивчику будет существенно быстрее, чем инициализировать портянку классов Linq.

Если последовательности более-менее крупные, то list1 можно скопировать в массив пар "значение - индекс", отсортировать по значению и бинарным поиском находить элементы. Получите сложность O(log N).

Если же последовательности могут быть очень большими, то по list1 можно построить хеш-таблицу вида "значение - индекс в оригинальном массиве" и за О(1) находить позиции элементов из list2.

Добавлено через 2 минуты
Действительно линейное время вы получите только, если обе последовательности будут отсортированы. Тогда можно их обе перебрать за один проход (Merge).

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,641 Записей в блоге: 14

	За линейное время заменить каждый элемент list1 его номером в list2 24.03.2019, 17:45. Показов 998. Ответов 6 Метки нет (Все метки) Например, list1: { 147, 256, 147, 333, 256, 168, 961, 256, 729, 961, 333 }; list2: { 147, 256, 333, 168, 961, 729 }. Выход: { 0, 1, 0, 2, 1, 3, 4, 1, 5, 4, 2 }. То есть каждый элемент выхода равен list2.IndexOf(list1[i]), но если так буквально и записать, время будет квадратичным. А может ли Linq сделать его линейным? 0

@Соколиный глаз Alvin Seville 343 / 273 / 134 Регистрация: 25.07.2014 Сообщений: 4,537 Записей в блоге: 22
	24.03.2019, 17:49
	Почему квадратичным? За одну операцию знамены номером оно будет линейным. Для оптимизации можно кешироваать пары "число - номер" в словарь и при каждой операции замены номером смотреть кеширована ли пара и если да, то брать номер из словаря иначе искать. 0

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,641 Записей в блоге: 14
	24.03.2019, 17:51 [ТС]
	А мне нужно, чтобы не за одну операцию, а общее время выполнения было линейным. 0

@Usaga 14303 / 9388 / 1354 Регистрация: 21.01.2016 Сообщений: 35,398
	25.03.2019, 07:46
	Etyuhibosecyu, если последовательности малы (как на примере в первом посте), то `IndexOf` будет самым эффективным решением. Значительно эффективнее Linq или чего-то другого. Не забывайте (или знайте), что Linq - пачка итераторов разной степени упоротости. Эти итераторы - классы, объекты которых нужно создать, методы которых нужно вызывать. Потом её и мусор для GC будет. Шесть раз пробежаться по маленькому массивчику будет существенно быстрее, чем инициализировать портянку классов Linq. Если последовательности более-менее крупные, то `list1` можно скопировать в массив пар "значение - индекс", отсортировать по значению и бинарным поиском находить элементы. Получите сложность O(log N). Если же последовательности могут быть очень большими, то по `list1` можно построить хеш-таблицу вида "значение - индекс в оригинальном массиве" и за О(1) находить позиции элементов из `list2`. Добавлено через 2 минуты Действительно линейное время вы получите только, если обе последовательности будут отсортированы. Тогда можно их обе перебрать за один проход (Merge). 1