按最大距离对数组排序 [英] Sorting array by max distance

问题描述

我有一个唯一整数列表，我想对它们进行排序，以便下一个整数始终与其余所有整数保持尽可能远的距离，这是可能的.

I've got a list of unique integers, and I want to sort them so that the next integer is always as far from all the rest, an it's possible.

例如{1,2,3,4,5,6,7,8,9} => {1,9,6,2,8,3,7,4,5}

For example, {1,2,3,4,5,6,7,8,9} => {1,9,6,2,8,3,7,4,5}

我需要非常快地做到这一点.

And I need to do it really fast.

目前，我正在这样做:

    static double GetDistanceIndex(int value, List<int> others)
    {
        double result=0;
        foreach (var other in others)
        {
            result += Math.Sqrt(Math.Abs(other - value));
        }

        return result;
    }

    static List<int> Sort(List<int> items, int initialValue)
    {
        items = items.ToList();
        List<int> result=new List<int>();


        lock (rnd)
        {
            while (true)
            {
                result.Add(initialValue);
                items.Remove(initialValue);
                if (items.Count == 0)
                {
                    break;
                }
                Dictionary<double, List<int>> distances = new Dictionary<double, List<int>>();
                foreach (var item in items)
                {
                    var d = GetDistanceIndex(item, result);
                    if (!distances.ContainsKey(d))
                    {
                        distances[d] = new List<int>();
                    }
                    distances[d].Add(item);
                }

                var max = distances.Keys.Max();
                var l = distances[max];
                //if (l.Count == 1)
                //{
                //    initialValue = l[0];
                //}
                //else
                //{
                initialValue = l[rnd.Next(l.Count)];
                //} 
            } 
        }

        return result;
    }

但是问题是，像这样实现的算法对于大型数组将非常缓慢地工作.

But the problem is, that implemented like this, the algorithm will work extremely slowly for large arrays.

有人可以向我建议一种更好的方法吗?

Can anyone suggest to me a better way to do it?

更新

这里有一个更好的描述:

Here's a better description what was done:

{1,2,3,4,5,6,7,8,9} =>

{1,2,3,4,5,6,7,8,9}=>

1. 初始种子:1.实际上，它可以是任何数字.我们可以选择5，得到类似{5,9,1,2,8,3,7,6,4}
2. 从提供的数组中，9离1的距离最远
3. 由于列表中所有数字均与1和9等距，因此我们可以选择其中任意一个.我用rand选择6.
4. 现在我们正在寻找距离{1,9,6}最远的数字.选择2是因为 abs(2-1)+ abs(2-9)+ abs(2-6)= 12 并且大于 abs(3-1)+ abs(3-9)+ abs(3-6)= 11 或 abs(4-1)+ abs(4-9)+ abs(4-6)= 10 或abs(8-1)+ abs(8-9)+ abs(8-6)= 10 或 abs(7-1)+ abs(7-9)+ abs(7-6)= 9 或 abs(5-1)+ abs(5-9)+ abs(5-6)= 9
5. 等

更新1

我正在使用这种算法从固定数量的替代项中选择尽可能彼此不同的数字

I'm using this algorithm to select numbers as different from each other as possible from a fixed number of alternatives

更新2

公爵夫人在他的回答中指出，{1,9,2,8,3,7,4,6​​,5}也符合我的要求.这是真的，这是我的错误.我希望这些数字尽可能地间隔开，而3d数字与第一个数字非常接近并不是我想要的.所以我正在更新距离功能以反映这一点

Dukeling in his answer pointed out to me, that {1,9,2,8,3,7,4,6,5} also conforms to my requirements. This was true, and it's my mistake. I want the numbers to be as far spaced as possible, and 3d number being very close to the first one is not what I intended. So I'm updating the distance function to reflect this

推荐答案

[已编辑，以符合新的距离函数]

您正在通过重复调用GetDistanceIndex()来进行不必要的工作.请注意，您不需要每次都从头开始汇总所有内容.如果您有这样的数组:

You are making unnecessary work by calling GetDistanceIndex() repeatedly. Notice that you don't need to sum everything from scratch everytime. If you have an array like this:

[a，b，c，d，............，x]

[a, b, c, d, ............, x]

已经对a，b，c和d进行了排序，那么，当您插入新元素'e'时，未排序集中的任何位置'x'的距离函数的和将等于排序后的集合仅增加sqrt(abs(xe)).您不必从头开始重新计算整个金额.

Where a, b, c, and d are already sorted, then, when you insert a new element 'e', the sum of the distance function of any position 'x' in the unsorted set to all the other numbers in the sorted set is only increased by sqrt(abs(x-e)). You don't have to recompute the whole sum from scratch.

因此，这是如何对其进行优化的方法:使用某种方法来存储对(数字，距离).例如，如果使用的是C，则可以使用两个整数(值本身和到排序集的距离)组成一个结构数组.在每一步中，您都要遍历排序集中未存在的每一对(数字，距离)，并更新其distance属性.您可以同时跟踪最大值.一些伪代码:

So here's how you can optimize it: use some kind of method to store a pair (number, distance). If you were using C, you could, for example, make an array of a structure with two integers, the value itself, and the distance to the sorted set. At each step, you go through every pair (number, distance) that is not in the sorted set and you update its distance attribute. You can keep track of the maximum at the same time. Some pseudo-code:

• 创建一个辅助缓冲区S，以容纳(数字，距离)对；

• Create an auxiliary buffer S, to hold pairs of (number, distance);

插入与S中的initialValue不同的每个数字x，距离= sqrt(abs(initialValue-x)).同时跟踪最大值m；

Insert every number x different from initialValue in S, with distance = sqrt(abs(initialValue - x)). Keep track of the maximum, m, at the same time;

在每个步骤中，选择m并将其移动到数组的已排序部分.从S中删除它.然后，转到S中的每个元素y并添加sqrt(abs(y.number-m.number))到y的距离.同样，您需要保持跟踪您这样做的最大数量.不断重复，直到每个元素已排序.

In each step, pick m and move it to the sorted piece of the array. Remove it from S. Then, go to every element y in S and add sqrt(abs(y.number-m.number)) to y's distance. Again, you need to keep track of the maximum as you do this. Keep repeating that until every element is sorted.

这不是一个出色的解决方案.它在O(n ^ 2)中运行，但是您当前的算法在O(n ^ 3)中运行，因为GetDistanceIndex()始终从头开始.另外，我不会使用列表和字典，而是尝试使用一个简单的数组，以便您可以在恒定时间内访问和删除元素.从列表中删除可能是低效率的，它永远不会比O(log(n))更好.

It's not a brilliant solution; it runs in O(n^2), but your current algorithm runs in O(n^3) because GetDistanceIndex() always starts from scratch. Also, I wouldn't use lists and dictionaries, try to use a simple array, so that you can access and delete elements in constant time. Deleting from a list can be inefficient, it never gets better than O(log(n)).

目前，这是我能想到的唯一优化方法，也许有人会有更好的主意.

At the moment, that's the only optimization I can think of, maybe someone will have a better idea.

这篇关于按最大距离对数组排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！