Как быстро вставить int в отсортированный массив?

Question

Я хотел бы вставить int в отсортированный массив.Эта операция будет выполняться очень часто, поэтому она должна быть максимально быстрой.

• Возможно и даже предпочтительнее использовать List или любой другой класс вместо массива
• Все значения находятся в диапазоне от 1 до 34
• Массив обычно содержит ровно 14 значений

Я думал о многих различных подходах, включая бинарный поиск и простую вставку-копировать, но было трудно решить.Кроме того, я чувствовал, что пропустил идею.У вас есть опыт в этой теме или есть какие-то новые идеи для рассмотрения?

Answer 1

Я буду использовать массив int длиной 35 (потому что вы указали диапазон 1-34) для записи состояния чисел.

int[] status = Enumerable.Repeat(0, 35).ToArray(); 
//an array contains 35 zeros
//which means currently there is no elements in the array
status[10] = 1;  // now the array have only one number: 10
status[11] ++;   // a new number 11 is added to the list

Так что если вы хотите добавить число i кlist:

status[i]++;  // O(1) to add a number

Чтобы удалить i из списка:

status[i]--;   // O(1) to remove a number

Хотите знать все цифры в списке?

    for (int i = 0; i < status.Length; i++)
    {
        if (status[i] > 0)
        {
            for (int j = 0; j < status[i]; j++)
                Console.WriteLine(i);
        }
    }
    //or more easier using LINQ
    var result = status.SelectMany((i, index) => Enumerable.Repeat(index, i));

Следующий примерможет помочь вам лучше понять мой код:

the real number array: 1 12 12 15 9 34 // i don't care if it's sorted
the status array: status[1]=1,status[12]=2,status[15]=1,status[9]=1,status[34]=1
                  all others are 0

Answer 2

При 14 значениях это довольно маленький массив, я не думаю, что переключение на более разумную структуру данных, такую ​​как список, выиграет вам многое, особенно если вы быстро получаете хороший произвольный доступ. Даже бинарный поиск на самом деле может быть медленнее, чем линейный поиск в этом масштабе. Вы уверены, что, скажем, вставка при копировании не удовлетворяет вашим требованиям к производительности?

Answer 3

Для вставки в середину, LinkedList<int> будет самым быстрым вариантом - все остальное включает копирование данных.На 14 элементах, не беспокойтесь о бинарном поиске и т. Д. - просто идите вперед к нужному элементу:

using System;
using System.Collections.Generic;
static class Program
{
    static void Main()
    {

        LinkedList<int> data = new LinkedList<int>();
        Random rand = new Random(12345);
        for (int i = 0; i < 20; i++)
        {
            data.InsertSortedValue(rand.Next(300));
        }
        foreach (int i in data) Console.WriteLine(i);
    }
}
static class LinkedListExtensions {
    public static void InsertSortedValue(this LinkedList<int> list, int value)
    {
        LinkedListNode<int> node = list.First, next;
        if (node == null || node.Value > value)
        {
            list.AddFirst(value);
        }
        else
        { 
            while ((next = node.Next) != null && next.Value < value)
                node = next;
            list.AddAfter(node, value);
        }
    }
}

Answer 4

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

То, что вы замечаете, происходит "очень часто", часто не узкие места в программе - часто удивительно, каковы фактические узкие места.Вы должны написать что-то простое и измерить фактическую производительность вашей программы перед выполнением каких-либо оптимизаций.

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

Предполагая, что это узкое место, производительность big-O различных методов здесь не будет актуальна из-за небольшого размера вашего массива.Проще всего попробовать несколько разных подходов, измерить результаты, посмотреть, какие из них наиболее эффективны, и выбрать этот метод.Если вы следовали совету из первого абзаца, у вас уже есть настройка профилировщика, которую вы также можете использовать для этого шага.

Answer 5

Запись метода берет массив целых чисел и сортирует их на месте с помощью Bubble Sort. Метод не имеет права создавать какие-либо дополнительные массивы. Bubble Sort - это простой алгоритм сортировки, который работает по циклу сортируемого массива, сравнивая каждую пару смежных элементов и меняя их местами, если они находятся в неправильном порядке.

Answer 6

У вас есть диапазон возможных значений от 1 до 34, который довольно узок.Таким образом, самый быстрый способ, вероятно, будет использовать массив с 34 слотами.Чтобы вставить число n, просто сделайте массив [n-1] ++ и удалите его, сделайте массив [n.1] - (если n> 0).

Чтобы проверить, существует ли значение в вашей коллекцииВы делаете массив [n-1]> 0.

edit : Черт ... Дэнни был быстрее.:)

Answer 7

Если в массиве нет повторяющихся значений и возможные значения не изменятся, возможно, хорошим выбором будет массив с фиксированным размером, в котором значение равно индексу

И вставка, и чтение - O (1)

Answer 8

Если вы работаете в .Net 4, вам стоит взглянуть на SortedSet<T>.В противном случае посмотрите на SortedDictionary<TKey, TValue>, где вы делаете TValue как object и просто вставляете null, потому что вас просто интересуют ключи.

Answer 9

Какая самая распространенная операция с вашим массивом?Включить?Читай?

• Структура данных кучи даст вам O (log (14)) для них обоих.SortedDictionary может повлиять на вашу производительность.
• Использование простого массива даст вам O (1) для чтения и O (14) для вставки.

Кстати, вы пробовали System.Collections.Generic.SortedDictionary от System.Collections.Generic.SortedList?

Answer 10

Лучше всего использовать подход грубой силы, потому что 14 - это не число :).Однако это не масштабируемое решение, так как 14 должно стать 14000 за один день, что вызовет проблемы