Быстрый поиск количества элементов в массиве

Question

У меня есть массив, размер может быть до 10000. Он держит только 1/2/3/4. Мне нужно найти, сколько 1s, 2s, 3s и 4s есть в массиве. Какой самый быстрый способ сделать это? Мой язык использования - Java. Мой кусок кода -

for(int i=0; i<myArray.length;i++){
            int element = myArray[i];
            if(element == 1){
                onesCount++;
            }
            else if(element == 2){
                twosCount++;
            }
            else if(element == 3){
                threesCount++;
            }
            else
                foursCount++;
}

Я надеюсь, что есть хорошее решение.

Answer 1

int count[5]; //initialize this to 0
for(int i = 0; i<n; i++)
{
count[array[i]]+=1;
}

Answer 2

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

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

Answer 3

У вас будут отдельные счетчики для записей массива.Каждый из них будет увеличиваться при обнаружении нового совпадающего номера, поэтому вы должны посещать каждый индекс хотя бы один раз , то есть у вас будет алгоритм, работающий за O (n) раз.Оператор Switch может быть предпочтительнее, чем несколько операторов if-else:

int[] array = new int[10000];
// ... populate array
int[] counters = new int[4];

for (int i = 0; i < array.length; i++)
{
    int temp = array[i];
    switch (temp) {
    case 1:
        counters[0]++;
        break;
    case 2:
        counters[1]++;
        break;
    case 3:
        counters[2]++;
        break;
    case 4:
        counters[3]++;
        break;
    default:
        // to do.
    }
}

Answer 4

Если вы используете Java 7, вы можете использовать Fork / Join Framework .Сложность все равно будет O (n) ... но она может быть быстрее для большого массива

Answer 5

Я не думаю, что вы будете быстрее, чем это:

final int[] counts = new int[5];
final int length = array.length - 1;
for (int i = 0; i < length; i++) {
   counts[array[i]]++;
}

Обратите внимание, что в цикле для на array.length нет ссылок. Он помещается в локальный финальный тип int, это позволяет избежать разыменования array.length в каждой итерации.

Я сравнил это с этим методом, который использует оператор switch..case и только локальные переменные стека:

    int count1 = 0;
    int count2 = 0;
    int count3 = 0;
    int count4 = 0;

    for (int i = array.length - 1; i >= 0; i--) {
        switch (array[i]) {
        case 1:
            count1++;
            break;
        case 2:
            count2++;
            break;
        case 3:
            count3++;
            break;
        case 4:
            count4++;
            break;
        }
    }

Результаты показали, что первый метод занял 17300 наносекунд, а метод switch..case - 79800 наносекунд. [ОБНОВЛЕНО: забыл разделить наносекунды на 10. Я запускал каждый метод 10 раз.]

Примечание: перед тем, как проводить бенчмаркинг, я предупреждал виртуальную машину.

Answer 6

если версия коммутатора (депортировщик) или версия noMAD не самая лучшая, попробуйте это:

for (int i = 0; i < myArray.length; i++) {
    int element = myArray[i];
    if (element > 2) {
        if (element == 4) {
            foursCount++;
        } else 
            threesCount++;
    } else {
        if (element == 2) 
            twosCount++;
        else 
            onesCount++; 
    }
}

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

Кроме того, использование параллелизма всегда стоит попробовать для больших данных.

Answer 7

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

Answer 8

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

Просто создайте для себя массив из четырех элементов, каждый из которых представляет одно из ваших значений (1/2/3/4), и для каждого элемента в исходном массиве вы увеличиваете количество в соответствующем месте в массиве «count». Это сделало бы это O (n).