Можно ли посчитать количество элементов из одного массива в другом и наоборот в одном цикле?

Question

У меня есть двойной массив х и двойной массив у.Оба могут иметь дубликаты элементов.

const double MAX = 10000.0;
const int X_LENGTH = 10000;
const int Y_LENGTH = 10000;
const double TOLERANCE = 0.01;

Random random = new Random();

double[] x = new double[X_LENGTH];
for(int i = 0; i < X_LENGTH; i++)
{
        x[i] = MAX * random.NextDouble();
}

double[] y = new double[Y_LENGTH];
for(int j = 0; j < Y_LENGTH; j++)
{
        y[j] = MAX * random.NextDouble();
}

Я пытаюсь подсчитать, сколько элементов в массиве x найдено в массиве y в пределах допуска, и сколько элементов в массиве y найдено в массиве x в пределах одного и того жетолерантность.Обратите внимание, что эти цифры могут быть разными.Самый простой способ сделать это с помощью двух наборов из двух встроенных циклов:

int x_matches = 0;
for(int i = 0; i < X_LENGTH; i++)
{
        for(int j = 0; j < Y_LENGTH; j++)
        {
                if(Math.Abs(x[i] - y[j]) <= TOLERANCE)
                {
                        x_matches++;
                        break;
                }
        }
}

int y_matches = 0;
for(int j = 0; j < Y_LENGTH; j++)
{
        for(int i = 0; i < X_LENGTH; i++)
        {
                if(Math.Abs(x[i] - y[j]) <= TOLERANCE)
                {
                        y_matches++;
                        break;
                }
        }
}

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

Array.Sort(x);
Array.Sort(y);

int x_matches_2 = 0;
int i2 = 0;
int j2 = 0;
while(i2 < X_LENGTH && j2 < Y_LENGTH)
{
        if(Math.Abs(x[i2] - y[j2]) <= TOLERANCE)
        {
                x_matches_2++;
                i2++;
        }
        else if(x[i2] < y[j2])
        {
                i2++;
        }
        else if(x[i2] > y[j2])
        {
                j2++;
        }
}

int y_matches_2 = 0;
int i3 = 0;
int j3 = 0;
while(i3 < X_LENGTH && j3 < Y_LENGTH)
{
        if(Math.Abs(x[i3] - y[j3]) <= TOLERANCE)
        {
                y_matches_2++;
                j3++;
        }
        else if(x[i3] < y[j3])
        {
                i3++;
        }
        else if(x[i3] > y[j3])
        {
                j3++;
        }
}

Мне интересно, знает ли кто-нибудь способ объединения этих двух циклов в один и при этом получить один и тот же ответ.Я могу только придумать это:

int x_matches_2 = 0;
int y_matches_2 = 0;
bool[] y_matched = new bool[Y_LENGTH];
for(int i = 0; i < X_LENGTH; i++)
{
        bool x_matched = false;

        for(int j = 0; j < Y_LENGTH; j++)
        {
                if(Math.Abs(x[i] - y[j]) <= TOLERANCE)
                {
                        if(!x_matched)
                        {
                                x_matches_2++;
                                x_matched = true;
                        }
                        if(!y_matched[j])
                        {
                                y_matches_2++;
                                y_matched[j] = true;
                        }
                }
        }
}

Не требует сортировки;однако, в конечном итоге это происходит медленнее, потому что нужно проводить больше сравнений.

PS Это упрощение моей реальной проблемы, но я думаю, что решение этой проблемы будет применимо к обоим.

Answer 1

Создайте HashSet<int> для обоих массивов и заполните их элементами массивов. Обходите оба массива, ищите элементы в соответствующем (противоположном) HashSet - HashSet поиске - O (1), поэтому общее усилие - O (m + n), где m - размеры массива.

Answer 2

Похоже, что это должно быть O (n * m) в худшем случае - все элементы одного массива "похожи" на все элементы другого массива - вы должны выполнить сравнение для каждой пары.

Поскольку у вас уже есть сортировка, рассмотрите возможность разделения каждого массива на диапазоны (т. Е. 20 диапазонов с примерно 50 числами в каждом [0, 0,05), [0,05, 0,1), .. [0,95, 1]), чтобы вы могли сравнивать диапазоны Сначала, а затем сравните отдельные числа - в зависимости от данных (хорошо работает со случайным или другим распределением без огромных скоплений значений), вы можете значительно уменьшить количество сравнений.

Answer 3

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

public static void JustDoIt(double[] x, double[] y)
{
    Array.Sort(x);
    Array.Sort(y);

    bool mustContinue = true;
    bool isXTurns;
    bool withinTolerance;

    int lastBase_x = 0;
    int lastBase_y = 0;

    int lastMatch_x = 0;
    int lastMatch_y = 0;

    int current_x = 0;
    int current_y = 0;

    int matchedCount_x = 0;
    int matchedCount_y = 0;

    double yourTolerance = 0.001;

    while (mustContinue)
    {
        isXTurns = x[current_x] <= y[current_y];

        if (isXTurns)
        {
            withinTolerance = (y[current_y] - x[current_x] <= yourTolerance);
        }
        else
        {
            withinTolerance = (x[current_x] - y[current_y] <= yourTolerance);
        }

        if (withinTolerance)
        {
            if (isXTurns)
            {
                if (current_x > lastMatch_x)
                {
                    matchedCount_x++;
                    lastMatch_x = current_x;
                }

                if (current_y > lastMatch_y)
                {
                    matchedCount_y++;
                    lastMatch_y = current_y;
                }

                if (current_y + 1 < y.Length)
                {
                    current_y++;
                }
                else if (current_x + 1 < x.Length)
                {
                    current_x++;
                }
                else
                {
                    mustContinue = false;
                }

            }
            else
            {
                if (current_y > lastMatch_y)
                {
                    matchedCount_y++;
                    lastMatch_y = current_y;
                } 

                if (current_x > lastMatch_x)
                {
                    matchedCount_x++;
                    lastMatch_x = current_x;
                }

                if (current_x + 1 < x.Length)
                {
                    current_x++;
                }
                else if (current_y + 1 < y.Length)
                {
                    current_y++;
                }
                else
                {
                    mustContinue = false;
                }
            }

        }
        else
        {
            if (isXTurns)
            {
                lastBase_x++;
                mustContinue = lastBase_x < x.Length;
            }
            else
            {
                lastBase_y++;
                mustContinue = lastBase_y < y.Length;
            }

            current_x = lastBase_x;
            current_y = lastBase_y;
        }
    }
}

Некоторые странные результаты, которые вы получите: если у вас есть 2 массива по 2 элемента в каждом, возможно, что у вас более двух совпадений от x до y или от y до x.Это происходит потому, что x [0] может совпадать с y [0] и y [1], так же как и x [1].Таким образом, вы получите 4 матча в обоих «направлениях».Например, когда я запускал этот код с двумя массивами по 1000 элементов в каждом, у меня было 1048 совпадений в одном и 978 совпадений в другом.Я надеюсь, что это поможет.

Редактировать : Вот общая версия:

public static void JustDoIt<T>(IEnumerable<T> items_x, IEnumerable<T> items_y, out int matchedCount_x, out int matchedCount_y, IComparer<T> comparer, Func<T, T, bool> toleranceReferee)
{

    T[] x = items_x.OrderBy(item => item, comparer).ToArray();
    T[] y = items_y.OrderBy(item => item, comparer).ToArray();

    bool mustContinue = true;
    bool isXTurns;
    bool withinTolerance;

    int lastBase_x = 0;
    int lastBase_y = 0;

    int lastMatch_x = 0;
    int lastMatch_y = 0;

    int current_x = 0;
    int current_y = 0;

    matchedCount_x = 0;
    matchedCount_y = 0;

    while (mustContinue)
    {
        isXTurns = comparer.Compare(x[current_x], y[current_y]) <= 0;

        withinTolerance = toleranceReferee(x[current_x], y[current_y]);

        if (withinTolerance)
        {
            if (isXTurns)
            {
                if (current_x > lastMatch_x)
                {
                    matchedCount_x++;
                    lastMatch_x = current_x;
                }

                if (current_y > lastMatch_y)
                {
                    matchedCount_y++;
                    lastMatch_y = current_y;
                }

                if (current_y + 1 < y.Length)
                {
                    current_y++;
                }
                else if (current_x + 1 < x.Length)
                {
                    current_x++;
                }
                else
                {
                    mustContinue = false;
                }

            }
            else
            {
                if (current_y > lastMatch_y)
                {
                    matchedCount_y++;
                    lastMatch_y = current_y;
                }

                if (current_x > lastMatch_x)
                {
                    matchedCount_x++;
                    lastMatch_x = current_x;
                }

                if (current_x + 1 < x.Length)
                {
                    current_x++;
                }
                else if (current_y + 1 < y.Length)
                {
                    current_y++;
                }
                else
                {
                    mustContinue = false;
                }
            }

        }
        else
        {
            if (isXTurns)
            {
                lastBase_x++;
                mustContinue = lastBase_x < x.Length;
            }
            else
            {
                lastBase_y++;
                mustContinue = lastBase_y < y.Length;
            }

            current_x = lastBase_x;
            current_y = lastBase_y;
        }
    }
}

С примером того, как вы бы назвали его для int:

List<int> x2 = new List<int>() { 2, 4, 4, 6, 9, 9 };    // To test an IEnumerable
IEnumerable<int> y2 = new int[] { 1, 3, 3, 4, 6, 9 };   // To test another

int xcount;
int ycount;

SingleLoop.JustDoIt(
    x2,
    y2,
    out xcount,
    out ycount,
    Comparer<int>.Default,
   (currentX, currentY) => { return currentX == currentY; });

Answer 4

Если ваши данные на самом деле находятся в диапазоне [0..1], как Random.NextDouble(), то вы можете просто создать массив с 1000 (= 1 / TOLERANCE) корзинами, по одному на каждые [x..x + TOLERANCE] Диапазон в общем диапазоне. Поместите каждое значение в одном массиве в его корзину. Затем перейдите к другому массиву и сравните каждое значение с содержимым ближайшего бина, бина до и одного после.

Редактировать в ответ на измененный вопрос : Вместо использования плоского массива с элементами Range / Tolerance вы можете использовать хеш-таблицу: используйте HashFunction(x/Tolerance) в качестве ключа хеша для элементов x в первый массив, затем сравните каждый элемент y во втором массиве с элементами, хранящимися для хэшей HashFunction(y/Tolerance-1), HashFunction(y/Tolerance), HashFunction(y/Tolerance+1). Теоретически, доступ к хеш-таблице равен O (1), поэтому вся операция будет O (m + n)