C структура данных для имитации Списка C# <Список <интервал>>?

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

Также, как Вы будете называть этот код.. это будут часто называть (например, в цикле?) Если так, упорядочивание данных назад и вперед может больше, чем сместить любое увеличение производительности.

Продолжить

Смотрите на Собственный код, не жертвуя производительностью.NET за некоторые interop опции. Существуют пути к interop без слишком большого количества потери производительности, но те interops могут только произойти с самым простым из типов данных.

Хотя я все еще думаю, что необходимо исследовать ускорение кода с помощью прямой.NET.

Продолжите 2

Кроме того, могу я предполагать что, если у Вас есть свое сердце при смешивании собственного кода и управляемого кода, что Вы создаете свою библиотеку с помощью c ++/cli. Ниже простой пример. Обратите внимание, что я не c ++/cli парень, и этот код не делает ничего полезного... его просто предназначенный, чтобы показать, как легко можно смешать собственный и управляемый код.

#include "stdafx.h"

using namespace System;

System::Collections::Generic::List<int> ^MyAlgorithm(System::Collections::Generic::List<int> ^sourceList);


int main(array<System::String ^> ^args)
{
    System::Collections::Generic::List<int> ^intList = gcnew System::Collections::Generic::List<int>();

    intList->Add(1);
    intList->Add(2);
    intList->Add(3);
    intList->Add(4);
    intList->Add(5);

    Console::WriteLine("Before Call");
    for each(int i in intList)
    {
        Console::WriteLine(i);
    }

    System::Collections::Generic::List<int> ^modifiedList = MyAlgorithm(intList);

    Console::WriteLine("After Call");
    for each(int i in modifiedList)
    {
        Console::WriteLine(i);
    }
}


System::Collections::Generic::List<int> ^MyAlgorithm(System::Collections::Generic::List<int> ^sourceList)
{
    int* nativeInts = new int[sourceList->Count];

    int nativeIntArraySize = sourceList->Count;

    //Managed to Native
    for(int i=0; i<sourceList->Count; i++)
    {
        nativeInts[i] = sourceList[i];
    }

    //Do Something to native ints
    for(int i=0; i<nativeIntArraySize; i++)
    {
        nativeInts[i]++;
    }


    //Native to Managed
    System::Collections::Generic::List<int> ^returnList = gcnew System::Collections::Generic::List<int>();
    for(int i=0; i<nativeIntArraySize; i++)
    {
        returnList->Add(nativeInts[i]);
    }


    return returnList;
}

Что заставляет Вас думать, что Вы получите скорость путем вызова в код C? C не волшебно быстрее, чем C#. Это может быть, конечно, но это может также легко быть медленнее (и более с ошибками). Особенно, когда Вы включаете в вызовы p/invoke в собственный код, совсем не бесспорно, что этот подход ускорит что-либо.

В любом случае C не имеет ничего как Список. Это имеет необработанные массивы и указатели (и Вы могли утверждать, что интервал ** более или менее эквивалентен), но Вы - вероятно, более обеспеченное использование C++, который действительно имеет эквивалентный datastructures. В частности, станд.:: вектор. Нет никаких простых способов выставить эти данные C# однако, так как это будет рассеяно в значительной степени случайным образом (каждый список является указателем на некоторую динамично выделенную память где-нибудь),

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

Править:

Я вижу несколько вещей в Вашем алгоритме, которые кажутся субоптимальными. Построение списка списков не является бесплатным. Возможно, можно создать единственный список и использовать различные смещения для представления каждого подсписка. Или возможно использование 'возврата урожая' и IEnumerable вместо того, чтобы явно создать списки могло бы быть быстрее.

Вы представили свой код, узнали, где время проводится?

Кроме того, убедитесь, что перемещение в C/C++ действительно, что необходимо сделать для скорости для начала. Оснастите исходный метод C# (автономный, выполняемый через модульные тесты), оснастите новый метод C/C++ (снова, автономный через модульные тесты) и посмотрите, каково различие в реальном мире.

Причина я поднимаю это, состоит в том, что я боюсь, что это может быть pyrhhic победа - использование совета Smokey Bacon, Вы получаете свой класс списка, Вы находитесь в "более быстром" C++, но существует все еще стоимость для вызова что DLL: Возврат из времени выполнения с P/Invoke или взаимодействующими с COM переносами довольно существенная производительность стоится.

Убедитесь, что Вы получаете свой "денежный эквивалент" из того перехода, прежде чем Вы сделаете это.

Обновление на основе Обновления OP

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

Я действительно думаю, учитывая описание проблемы, что проблема не то, что C#/.NET "медленнее", чем C, но более вероятно что код должен быть оптимизирован. Как другой плакат, здесь упомянутый, можно использовать указатели в C# для серьезного повышения производительности в этом виде цикла без потребности в маршалинге. Я изучил бы это сначала, перед вскакиванием в комплекс interop мир, для этого сценария.

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

Даже при том, что это 'небезопасно', это не менее 'безопасно', чем C/C++, и существенно легче разобраться.

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

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

static class PowerSet<T>
{
    static long[] mask = { 1L << 0, 1L << 1, 1L << 2, 1L << 3, 
                           1L << 4, 1L << 5, 1L << 6, 1L << 7, 
                           1L << 8, 1L << 9, 1L << 10, 1L << 11, 
                           1L << 12, 1L << 13, 1L << 14, 1L << 15, 
                           1L << 16, 1L << 17, 1L << 18, 1L << 19, 
                           1L << 20, 1L << 21, 1L << 22, 1L << 23, 
                           1L << 24, 1L << 25, 1L << 26, 1L << 27, 
                           1L << 28, 1L << 29, 1L << 30, 1L << 31};
    static public IEnumerable<IList<T>> powerset(T[] currentGroupList)
    {
        int count = currentGroupList.Length;
        long max = 1L << count;
        for (long iter = 0; iter < max; iter++)
        {
            T[] list = new T[count];
            int k = 0, m = -1;
            for (long i = iter; i != 0; i &= (i - 1))
            {
                while ((mask[++m] & i) == 0)
                    ;
                list[k++] = currentGroupList[m];
            }
            yield return list;
        }
    }
}

Затем Ваш клиентский код похож на это:

    static void Main(string[] args)
    {
        int[] intList = { 1, 2, 3, 4 };
        foreach (IList<int> set in PowerSet<int>.powerset(intList))
        {
            foreach (int i in set)
                Console.Write("{0} ", i);
            Console.WriteLine();
        }
    }

Я даже добавлю алгоритм битового жонглирования с шаблонными аргументами бесплатно. Для добавленной скорости можно перенести powerlist () внутренний цикл в небезопасном блоке. Это не имеет большого значения.

На моей машине этот код немного медленнее, чем код OP, пока наборы не равняются 16 или больше. Однако все случаи к 16 элементам составляют меньше чем 0,15 секунды. В 23 элементах это работает в 64% времени. Исходный алгоритм не работает на моей машине для 24 или больше элементов - это исчерпывает память.

Этот код занимает 12 секунд для генерации степенного множества для номеров 1 - 24, опуская время экрана I/O. Это - 16 миллионов выходов за 12 секунд, или о 1400K в секунду. Для миллиарда (который является тем, что Вы заключили в кавычки ранее), который составит приблизительно 760 секунд. Сколько времени Вы думаете, что это должно взять?

Это должен быть C, или действительно ли C++ является опцией также? Если C++, Вы можете просто его собственное list введите от STL. Иначе необходимо будет реализовать собственный список - ищут связанные списки или динамично измеренные массивы для указателей о том, как сделать это.

Ниже алгоритм C#, который должен быть намного быстрее (и использовать меньше памяти), чем алгоритм, который Вы отправили. Это не использует аккуратный двоичный прием Ваш использование, и в результате код является хорошим битом дольше. Это имеет еще много for циклы, чем Ваш, и могли бы занять время или два продвижения через него с отладчиком к полностью grok он. Но это - на самом деле более простой подход, после того как Вы понимаете то, что это делает.

В качестве награды возвращенные наборы находятся в более "естественном" порядке. Это возвратило бы подмножества набора {1 2 3} в том же порядке, Вы перечислили их в своем вопросе. Это не было фокусом, но является побочным эффектом используемого алгоритма.

В моих тестах я нашел, что этот алгоритм был приблизительно в 4 раза быстрее, чем алгоритм, который Вы отправили для большого набора 22 объектов (который был столь большим, как я мог пойти на свою машину без чрезмерной перегрузки диска, скашивающей результаты слишком много). Одно выполненное ваше заняло приблизительно 15,5 секунд, и мой занял приблизительно 3,6 секунды.

Для меньших списков различие является менее явным. Для ряда только 10 объектов Ваш работал 10,000 раз приблизительно через 7,8 секунд, и мой занял приблизительно 3,2 секунды. Для наборов с 5 или меньшим количеством объектов они работают близко к тому же времени. Со многими повторениями, Ваш выполнения немного быстрее.

Так или иначе вот код. Извините это является таким длинным; я пытался удостовериться, что я прокомментировал это хорошо.

/* 
 * Made it static, because it shouldn't really use or modify state data.
 * Making it static also saves a tiny bit of call time, because it doesn't
 * have to receive an extra "this" pointer.  Also, accessing a local
 * parameter is a tiny bit faster than accessing a class member, because
 * dereferencing the "this" pointer is not free.
 * 
 * Made it generic so that the same code can handle sets of any type.
 */
static IList<IList<T>> PowerSet<T>(IList<T> set){
    if(set == null)
        throw new ArgumentNullException("set");

    /*
     * Caveat:
     * If set.Count > 30, this function pukes all over itself without so
     * much as wiping up afterwards.  Even for 30 elements, though, the
     * result set is about 68 GB (if "set" is comprised of ints).  24 or
     * 25 elements is a practical limit for current hardware.
     */
    int   setSize     = set.Count;
    int   subsetCount = 1 << setSize; // MUCH faster than (int)Math.Pow(2, setSize)
    T[][] rtn         = new T[subsetCount][];
    /* 
     * We don't really need dynamic list allocation.  We can calculate
     * in advance the number of subsets ("subsetCount" above), and
     * the size of each subset (0 through setSize).  The performance
     * of List<> is pretty horrible when the initial size is not
     * guessed well.
     */

    int subsetIndex = 0;
    for(int subsetSize = 0; subsetSize <= setSize; subsetSize++){
        /*
         * The "indices" array below is part of how we implement the
         * "natural" ordering of the subsets.  For a subset of size 3,
         * for example, we initialize the indices array with {0, 1, 2};
         * Later, we'll increment each index until we reach setSize,
         * then carry over to the next index.  So, assuming a set size
         * of 5, the second iteration will have indices {0, 1, 3}, the
         * third will have {0, 1, 4}, and the fifth will involve a carry,
         * so we'll have {0, 2, 3}.
         */
        int[] indices = new int[subsetSize];
        for(int i = 1; i < subsetSize; i++)
            indices[i] = i;

        /*
         * Now we'll iterate over all the subsets we need to make for the
         * current subset size.  The number of subsets of a given size
         * is easily determined with combination (nCr).  In other words,
         * if I have 5 items in my set and I want all subsets of size 3,
         * I need 5-pick-3, or 5C3 = 5! / 3!(5 - 3)! = 10.
         */
        for(int i = Combination(setSize, subsetSize); i > 0; i--){
            /*
             * Copy the items from the input set according to the
             * indices we've already set up.  Alternatively, if you
             * just wanted the indices in your output, you could
             * just dup the index array here (but make sure you dup!
             * Otherwise the setup step at the bottom of this for
             * loop will mess up your output list!  You'll also want
             * to change the function's return type to
             * IList<IList<int>> in that case.
             */
            T[] subset = new T[subsetSize];
            for(int j = 0; j < subsetSize; j++)
                subset[j] = set[indices[j]];

            /* Add the subset to the return */
            rtn[subsetIndex++] = subset;

            /*
             * Set up indices for next subset.  This looks a lot
             * messier than it is.  It simply increments the
             * right-most index until it overflows, then carries
             * over left as far as it needs to.  I've made the
             * logic as fast as I could, which is why it's hairy-
             * looking.  Note that the inner for loop won't
             * actually run as long as a carry isn't required,
             * and will run at most once in any case.  The outer
             * loop will go through as few iterations as required.
             * 
             * You may notice that this logic doesn't check the
             * end case (when the left-most digit overflows).  It
             * doesn't need to, since the loop up above won't
             * execute again in that case, anyway.  There's no
             * reason to waste time checking that here.
             */
            for(int j = subsetSize - 1; j >= 0; j--)
                if(++indices[j] <= setSize - subsetSize + j){
                    for(int k = j + 1; k < subsetSize; k++)
                        indices[k] = indices[k - 1] + 1;
                    break;
                }
        }
    }
    return rtn;
}

static int Combination(int n, int r){
    if(r == 0 || r == n)
        return 1;

    /*
     * The formula for combination is:
     *
     *       n!
     *   ----------
     *   r!(n - r)!
     *
     * We'll actually use a slightly modified version here.  The above
     * formula forces us to calculate (n - r)! twice.  Instead, we only
     * multiply for the numerator the factors of n! that aren't canceled
     * out by (n - r)! in the denominator.
     */

    /*
     * nCr == nC(n - r)
     * We can use this fact to reduce the number of multiplications we
     * perform, as well as the incidence of overflow, where r > n / 2
     */
    if(r > n / 2) /* We DO want integer truncation here (7 / 2 = 3) */
        r = n - r;

    /*
     * I originally used all integer math below, with some complicated
     * logic and another function to handle cases where the intermediate
     * results overflowed a 32-bit int.  It was pretty ugly.  In later
     * testing, I found that the more generalized double-precision
     * floating-point approach was actually *faster*, so there was no
     * need for the ugly code.  But if you want to see a giant WTF, look
     * at the edit history for this post!
     */

    double denominator = Factorial(r);
    double numerator   = n;
    while(--r > 0)
        numerator *= --n;

    return (int)(numerator / denominator + 0.1/* Deal with rounding errors. */);
}

/*
 * The archetypical factorial implementation is recursive, and is perhaps
 * the most often used demonstration of recursion in text books and other
 * materials.  It's unfortunate, however, that few texts point out that
 * it's nearly as simple to write an iterative factorial function that
 * will perform better (although tail-end recursion, if implemented by
 * the compiler, will help to close the gap).
 */
static double Factorial(int x){
    /*
     * An all-purpose factorial function would handle negative numbers
     * correctly - the result should be Sign(x) * Factorial(Abs(x)) -
     * but since we don't need that functionality, we're better off
     * saving the few extra clock cycles it would take.
     */

    /*
     * I originally used all integer math below, but found that the
     * double-precision floating-point version is not only more
     * general, but also *faster*!
     */

    if(x < 2)
        return 1;

    double rtn = x;
    while(--x > 1)
        rtn *= x;

    return rtn;
}

Я соглашаюсь с, "оптимизируют.NET сначала" мнение. Это является самым безболезненным. Я предполагаю, что, если бы Вы написали некоторый неуправляемый код.NET с помощью указателей C#, это было бы идентично выполнению C, за исключением VM наверху.

P папа:

Вы могли изменить свою Комбинацию () код к этому:

    static long Combination(long n, long r)
    {
        r = (r > n - r) ? (n - r) : r;
        if (r == 0)
            return 1;
        long result = 1;
        long k = 1;
        while (r-- > 0)
        {
            result *= n--;
            result /= k++;
        }

        return result;
    }

Это уменьшит умножение и шанс переполнения к минимуму.