Перебор неупорядоченных пар элементов, хранящихся в коллекции - PullRequest
Новая
       1

Перебор неупорядоченных пар элементов, хранящихся в коллекции

3 голосов
/ 11 сентября 2011

В C # у меня есть коллекция уникальных элементов, и я хочу эффективно выполнить некоторый код для каждой неупорядоченной пары.Например, если мой контейнер содержит {a, b, c}, неупорядоченными парами являются (a, b), (a, c) и (b, c).Проблема возникает в области выполнения 2-opt оптимизации, поэтому эффективность является проблемой.

  • Мое текущее решение выглядит так: 

    foreach(var a in container) 
{
    foreach(var b in container)
    {
        if (a < b)
        {
             // execute code    
        }
    }
 }

    Очевидно, этоможет быть легко изменено, если оператор [] доступен для получения i-го элемента (т. е. если базовая структура данных является списком). Но для всех других контейнеров решение зависит от существования некоторой функции сравнения и не оченьэффективный.

  • Я также пробовал формулировку, основанную на операторе LINQ, который генерирует каждую нужную пару ровно один раз.Однако, как и ожидалось, это было намного медленнее, чем при первом подходе.Это относится и к решению, использующему ElementAt.

Редактировать: вот (улучшенный) использованный код LINQ: 

var x = from a in container
        from b in container
        where a < b 
        select new KeyValuePair<int,int>(a,b);

Тем не менее выполнение выполняется медленнее в 3-5 раз по сравнению с другими решениями.

  • Вот способ, которым я бы сделал это в C ++ (получая хорошую эффективность): 

    for(auto it1 = container.begin(); it1!=container.end(); ++it1) 
{
    auto it2 = it1;
    for(++it2; it2!=container.end(); ++it2) 
    {
        // execute code    
    }
 }

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

ИмеетКто-нибудь лучше идея / решение?

Ответы [ 4 ]

1 голос
/ 11 сентября 2011

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

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

Вы также можете проверить, имеет ли контейнер тип IList<T>, и пропустить операцию копирования.

1 голос
/ 11 сентября 2011

Если вы не заботитесь о заказе, вы можете сделать это так: 

int i = 0;
foreach (var a in list)
{
    int j = 0;
    foreach (var b in list)
    {
        if (i <= j)
            break;

        // execute code    

        j++;
    }

    i++;
}

Если вы заботитесь о заказе, вы можете ограничиться коллекциями, в которых реализован IList<T>, который содержит оператор []. Или вы можете сначала скопировать коллекцию в List<T>, а затем работать с этим.

0 голосов
/ 12 сентября 2011

Поместите свои элементы в List или IList, и затем вы сможете получить к ним доступ, используя индексы, очень похожие на ваш код C ++.

for (int i = 0; i < container.Count(); i++)
for (int j = i+1; j < container.Count(); j++)
{
    var item1 = container.Item[i];
    var item2 = container.Item[j];
}

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

0 голосов
/ 11 сентября 2011

Перечислители в C # не совпадают с перечислителями C ++ из вашего вопроса. В C # у вас нет ни begin, ни end элементов контейнера. У вас есть только элемент Current и метод Next(). Например, он позволяет получить намного больше последовательностей - вы можете перечислять через бесконечность последовательности случайных чисел, которые, очевидно, не имеют ни начала, ни конца.

Итак, вы не можете сделать это в C #, как в коде C ++, используя только IEnumerable классы. Лучший способ сделать это - использовать интерфейс System.Collection.Generics.IList<T>. Многие типы (например, массивы) наследуют этот интерфейс.

Если вы используете IEnumerable, то внутри вашего типа вы (в большинстве случаев) перебираете некоторую коллекцию. Если вы сделаете это - вы можете просто реализовать интерфейс IList<T>.

Есть и другое решение - в C # списки и массивы ссылочных типов содержат только ссылку на объект. Итак, вы можете скопировать свои данные в локальный список и работать с ним. Но это зависит от вашей памяти и требований к производительности.

...