Алгоритм определения размера массива

Question

Как определить длину массива эффективным образом?

Если вы ищете способ получить размер массива или глобального в кэше Intersystems, я начал думать о том, как определить размер массива. С тех пор я нашел решение моей исходной задачи, но загадка определения размера эффективно массива до сих пор давало мне покоя, так вот что я придумал до сих пор:

1. Начать индекс 1.
2. Проверить значение в текущем индексе.
3. Если значение найдено, удвойте индекс.
4. Если значение не найдено, вычтите используемый второй-последний индекс.
5. Продолжите с шагом 4, уменьшив вычитаемое значение на каждой итерации, пока индекс не станет достаточно маленьким, чтобы снова найти значение.
6. Увеличение индекса на единицу до тех пор, пока значение не будет найдено.
7. Второй-последний индекс будет размером.

В качестве примера, давайте массив размера 52:

1 - OK 
2 - OK 
4 - OK 
8 - OK 
16 - OK 
32 - OK 
64 - OVER 
48 - OK (64-16) 
49 - OK 
50 - OK 
51 - OK 
52 - OK 
53 - OVER 

Это кажется справедливым, так как я получаю длину массива в 13 итераций, однако, если мой массив размер увеличивается до 63 это увеличило бы итерации на 10 - тот же размер, с которым увеличился массив.

Для довольно небольшого массива я могу считать, что стук, который я принимаю в последних нескольких циклах, является почти приемлемым, даже если длина массива только одна меньше, чем сила двух, но что произойдет, если я использую очень большие массив, скажем, с элементами 2097152 (2^21 - 1)? Это означает, что я нажму первый «over» в 21 итерации, доведю индекс до 1572864 и начну ОЧЕНЬ ДЛИННУЮ ЛОП (1572864 итераций). В этом примере я не совсем «выигрываю» все это.

Теперь я могу оптомизировать это, еще раз увеличив индекс по степеням двух, но все это заставило меня задуматься: есть ли лучший способ сделать это? Я даже дистанционно на правильном пути? Будет ли я лучше просто использовать статический размер увеличения?

Answer 1

Похоже, вы пытаетесь изобрести binary search. В вашем примере, как только 64 завершился неудачно, вы выполняете двоичный поиск в интервале между 32 и 64. Таким образом, после 48 следующего значения вы должны попробовать 56. После 56 сбоев вы вернетесь к 52.

В общем, вы должны иметь возможность получить размер массива до 2^n элементов не более чем на 2n итераций.

Answer 2

Вместо перехода через последние 2^(n-1) через (2^n) -1, выполните двоичный поиск этого пространства. Итак, в основном ваше последнее предложение .... В любом случае, вы определенно не хотите идти со статическим увеличением размера.

Случайное наблюдение: Cache ObjectScript выглядит ужасно для работы.

Answer 3

Вы должны немного изменить свой алгоритм.

1 Start at index 0. 
2 Add 1 to index 
4 Stash it 
5 Test for a value at the current index. 
6 If 
    a value is found, double the index, go to 4 
    else - if 
     current index = stashed index + 1, stashed index is the size of array, quit 
     else set the current index to a stashed value, go to 2 

Это будет эффективно работать не только до первого «над», но и до конца.

Answer 4

В кэш, если вы ищете размер одного массива размерности с целочисленным индексом все, что вам нужно сделать, это

W $ Заказать (Array («»), - 1)

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