Член массива устанавливает собственный индекс в массиве

Я пишу код, в котором член класса, если! = -1, устанавливает свою позицию в массиве. Если значение равно == -1, используется следующий свободный индекс (диапазон которого равен 0 и длине массива). В этом обзоре меня больше интересует алгоритм, делающий его более быстрым, точным и читаемым, чем что-либо еще. несмотря на то, что я использую C #, я хотел бы сохранить его простым, C-подобным и избегать таких вещей C #, как Linq и т. д. Если есть читаемый и более быстрый способ сделать это без valueSet флаг, было бы неплохо. Я просто добавил его, потому что после swap() При вызове замененные элементы будут посещены дважды со значением! = -1, что приведет к повторной установке ошибочного значения. Дайте мне знать, если что-то непонятно. Ниже приведен код с некоторыми функциями, который действует как unittests. Также приветствуются различные способы сделать это.

using System.Collections.Generic;
using System.Diagnostics;

namespace sort
{
    class Program
    {
        static void Main(string[] args)
        {
            t1();
            t2();
            t3();
            t4();
        }

        //test case 1
        static void t1()
        {
            var arr = new List<A>();
            arr.Add(new A(-1, "a"));
            arr.Add(new A(-1, "b"));
            arr.Add(new A(0, "c"));
            arr.Add(new A(-1, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(sortedArr));
        }

        // test case 2
        static void t2()
        {
            var arr = new List<A>();
            arr.Add(new A(-1, "a"));
            arr.Add(new A(-1, "b"));
            arr.Add(new A(-1, "c"));
            arr.Add(new A(-1, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(sortedArr));
        }

        // test case 3
        static void t3()
        {
            var arr = new List<A>();
            arr.Add(new A(0, "a"));
            arr.Add(new A(1, "b"));
            arr.Add(new A(2, "c"));
            arr.Add(new A(3, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(arr.ToArray()));
        }

        static void t4()
        {
            var arr = new List<A>();
            arr.Add(new A(-1, "a"));
            arr.Add(new A(1, "b"));
            arr.Add(new A(0, "c"));
            arr.Add(new A(-1, "d"));

            var sortedArr = doSort(arr.ToArray());
            Debug.Assert(isSorted(sortedArr));
        }

        // not meant to be very fast just to be used in the "unittest"
        static bool isSorted(A[] arr)
        {
            if(arr.Length == 0)
            {
                return false;
            }

            // this make sure the values is sequential, starting with 0
            // and the last value must be same value as array's length
            if(arr[0].index != 0 || arr[arr.Length - 1].index != arr.Length - 1)
            {
                return false;
            }

            // we have checked already if the first and last values
            // are sequential, no need to recheck here so
            // we loop from 1 to arr.length - 1
            for (int i = 1; i < arr.Length - 1; i++)
            {
                if(i + 1 > arr.Length &&
                  arr[i].index + 1 != arr[i + 1].index)
                {
                    return false;
                }
            }

            return true;
        }

        static A[] doSort(A[] arr)
        {
            for(int i = 0; i < arr.Length; i++)
            {
                initValue(arr, i);
            }

            return arr;
        }

        static void initValue(A[] arr, int i)
        {
            var e = arr[i];

            if(e.valueSet)
            {
                return; /* nothing to do, value initialized already */
            }

            // initialize to current index
            if(e.index == -1)
            {
                e.index = i;
            }
            // an explicit index was set, the value at i index
            // must be set to the value at e.index index
            else if(e.index != i)
            {
                swap(arr, i, e.index);
                // after the swap, that element may be left
                // unitialized. Do initialize now.
                initValue(arr, i);
            }

            e.valueSet = true;
        }

        static void swap(A[] arr, int i, int j)
        {
            // swap items
            var t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;

            // update indexes
            arr[i].index = i;
            arr[j].index = j;
        }
    }

    class A
    {
        public A(int i, string s)
        {
            index = i;
            value = s;
        }

        public override string ToString()
        {
            return string.Format("index = %d, value = %s", index, value);
        }

        public int index { get; set; }
        public string value { get; set; }
        public bool valueSet { get; set; }
    }
}

1 ответ
1

Обзор

  • В ваших тестовых случаях почему бы не использовать массив напрямую (new A[] { new A(-1, "a"), new A(-1, "b"), new A(0, "c"),... };) вместо List<A>.ToArray()?

  • В части isSorted , ожидаете ли вы, что возвращаемое значение будет false если (arr.Length == 0)? Или же Класс ArgumentException можно использовать здесь.

  • В class A, может быть Dictionary Класс можно использовать здесь. Сделайте TKey индексным и TValue это строка.

  • Ключи неизменны в Dictionary. Код изменяет индексы.

    — эспот

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *