Найти индекс n-го вхождения 1 в двоичный вектор (matlab) - PullRequest
Новая
       9

Найти индекс n-го вхождения 1 в двоичный вектор (matlab)

0 голосов
/ 10 ноября 2018

У меня есть двоичный вектор, подобный этому x = [0 0 1 1 1 1 1 1 1]. Я хочу найти индекс, скажем, 7-го 1, который равен 9.

Я знаю, что могу сделать это: 

y = find(x);
index = y(7);

Но что, если вектор огромен, и я хочу сохранить использование памяти? y = find(x) не будет использовать много памяти? Если так, есть ли способ обойти это?

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

Будет ли следующее решение хорошим решением? 

basis = [0 0 1 1 1 1 1 1 1];
basisIndex = 7;
correctIndex = getIndex(basisIndex, basis); % should be 9 when basisIndex = 7

function ret = getIndex(basisIndex, basis) 
    counter = 1;
    for value = find(basis) % iterate through [3, 4, 5, 6, 7, 8, 9]
        if counter == basisIndex
            ret = value;
            break;
        end
        counter = counter + 1;
    end
end

1 Ответ

0 голосов
/ 10 ноября 2018

Просто переберите x. Во-первых, он не создаст новый вектор y=find(x) (экономит память). Во-вторых, если basisIndex мало, оно будет более эффективным.

Предположим, x - это вектор 1e8 на 1. Давайте сравним find только с итерацией. 

basis = randi(2,1e8,1) - 1;
basisIndex = 7;

tic % your first method
y = find(basis);
index = y(basisIndex);
toc

tic % iterate through base
index = 1;
match = 0;
while true
    if basis(index)
        match = match + 1;
        if match == basisIndex
            break
        end
    end
    index = index + 1;     
end 
toc

выход 

Elapsed time is 1.214597 seconds.
Elapsed time is 0.000061 seconds.

Даже если basisIndex большой 

basisIndex = 5e7;

Результат итерации еще более эффективен 

Elapsed time is 1.250430 seconds. % use find
Elapsed time is 0.757767 seconds. % use iteration
...