нахождение за время меньше чем O (n) максимального значения при быстрой вставке / удалении в неупорядоченном списке

Question

код:

using System;
using System.Diagnostics;

namespace ConsoleApp1
{
    class Program
    {
        const int maxResult = 120; //this can change but hardcoded for this code

        static int poolPos;
        static double[] pool = new double[maxResult * 4];

        static int maxPos;
        static double[] result = new double[maxResult];


        static void Main(string[] args)
        {
            var sw = Stopwatch.StartNew();

            for(int i = 0; i  < 100_000; ++i)
                Unlock();

            Console.WriteLine(sw.ElapsedMilliseconds);

            //Console.Read();
        }

        static void Unlock()
        {
            int total = maxResult;

            //reset array
            poolPos = 0;
            maxPos = 0;

            FindLock(4);


            while (total-- > 0)
            {
                int i = 0;

                double maxWeight = pool[0];
                int pos = 0;

                while (++i < poolPos) //O(n), can it be faster?
                    if (pool[i] >= maxWeight) //can have duplicate value, find latest max inserted
                        (maxWeight, pos) = (pool[i], i); //keep track

                result[maxPos++] = maxWeight; //store the result
                pool[pos] = pool[--poolPos]; //remove from array by swapping it with last item in the array
                FindLock();
            }
        }

        //simulate what feed the array
        //don't look at this unless something should be done at insert time
        static Random rnd = new Random(42); 
        static void FindLock(int add = -1)
        {
            if(add == -1)
            {
                add = rnd.Next(1, 4);
            }

            for(int i = 0;i<add;++i)
            {
                pool[poolPos++] = rnd.Next(-500, 500) / 100d;
            }
        }
    }
}

результат профилирования:

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

Answer 1

По определению, если вы работаете с неупорядоченным списком, поиск элемента всегда будет O (1) в лучшем случае и O (n) в худшем.

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