в смысле поменять соседей?

это выглядит как просто другая случайная перестановка?..

Ну разбить на пары s_2i, s_2i+1. Сделать перестановку которая меняет их местами

эта идея мне приходила, но есть проблема в том, что s_2i+1 может указывать на элемент, где у нас хранится какая-та важная информация вроде части другой пары

Что?

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

2 0 1 3

после маппинга первой пары я получаю
2 . 0 .

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

Да, понял

я решил в итоге просто в 64-битном числе верхние биты использовать для пар, нижние для мапы

и вторым проходом занулить верхние биты

А какая разница по сравнению с двумя 32 битными массивами?)

что не надо аллоцировать второй массив

¯\_(ツ)_/¯

Ну возьми один в два раза больше)

То же самое только без ебли

знаю неслучайную обратимую перестановку, там просто у битов индекса меняется порядок на обратный
для 8 элементов:
0 - b000 - b000 - 0
1 - b001 - b100 - 4
2 - b010 - b010 - 2
3 - b011 - b110 - 6
4 - b100 - b001 - 1
5 - b101 - b101 - 5
6 - b110 - b011 - 3
7 - b111 - b111 - 7

Всем привет!
Столкнулся с следующей задачей.

Есть множество (пространство поиска) некоторых параметров


"a": [a1; a2 (default=a3)], ..., "f": [f1; f2 (default=f3)]

Назовём его V

В нем содержатся все параметры и все их возможные значения, а также значения по умолчанию.

Есть некоторый словарь (конфигурация)

Для определенности
W = {"a": val_a, ..., "f": val_f}

Есть некоторая функция F: V -> R+, которую мы можем посчитать. Она даёт некоторое значение для данного словаря.

Для неизвестных конфигов или значений для них положим
F(W)=+Inf

Задача:

Постпроцессинг. Необходимо найти вклад (вес) того или иного параметра с его значением в результат функции F(W).

Алгоритм такой:
У нас есть словарь W, выкинем из него все параметры с дефолтным значением, далее сгенерируем все подконфигурации размера |W| - 1 (Wi), посчитаем функцию F(W) для всех подконфигураций и выберем такую, что F(.) от нее -> min. Сохраним Wi, возьмем ее и будем повторять алгоритм пока не дойдём до W* = {}.

В чем проблема? Количество необходимых для замера F(.) конфигурации растет квадратично, а замер может быть достаточно долгим.
Архитектура приложения построена без асинхронности и многопоточности. (Кстати говоря, в общем-то, можно считать замеры F(W) i/o bound задачей, так как они выполняются на других девайсах).

Сконцентрируемся на самом алгоритме, нужно выполнить некоторые оптимизации.

На ум приходит следующее.
Сделаем некоторое упрощение, сказав, что

F({"a": val_a}) + F({"b": val_b}) = F({"a": val_a, "b", val_b})
То есть допустим некоторую независимость.

В данном предположении, скажем, что есть такие параметры в данных конфигурациях, которые имеют очень малый вес для F(W). Можно объединять такие параметры в один "Alias" и при постпроцессинге выкидывать сразу группу. Это должно снизить временные затраты. Как это лучше сделать?

На ум приходит какая-то линейная аппроксимация

Сделать замеры по отдельности F({"a": val_a}) F({"b": val_b}), ..., F({"f": val_f}) посчитать общую сумму, найти веса, ввести некоторый threshold и объединять в группы какие-то.

Есть ли какие-то идеи для такой задачи? Предложения для оптимизаций? В какую сторону алгоритмов лучше смотреть, или это больше в сторону машинного обучения?

Спасибо за ответ.

Привет всем, извините за оффтоп.
Я ищу ментора, наставника, гуру...
- Алгоритмы
- .Net
- Unity
- C#