Я хочу найти максимальную частоту общей цифры в последовательном подмножестве целочисленного массива

Question

Подпоследовательность частичных цифр в массиве A является подпоследовательностью целых чисел, в которой каждое последующее целое число имеет по крайней мере 1 общую цифру

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

public static void Main(string[] args)
{
    Dictionary<char, int> dct = new Dictionary<char, int>
    {
        { '0', 0 },
        { '1', 0 },
        { '2', 0 },
        { '3', 0 },
        { '4', 0 },
        { '5', 0 },
        { '6', 0 },
        { '7', 0 },
        { '8', 0 },
        { '9', 0 }
    };

    string[] arr = Console.ReadLine().Split(' ');
    for (int i = 0; i < arr.Length; i++)
    {
        string str = string.Join("", arr[i].Distinct());
        for (int j = 0; j < str.Length; j++)
        {
            int count = dct[str[j]];
            if (count == i || (i > 0 && arr[i - 1].Contains(str[j])))
            {
                count++;
                dct[str[j]] = count;
            }
            else dct[str[j]] = 1;
        }
    }
    string s = dct.Aggregate((l, r) => l.Value > r.Value ? l : r).Key.ToString();
    Console.WriteLine(s);
}

, например, 12 23 231 Ответ будет 2, потому что это происходит 3 раза

Массив может содержать 10 ^ 18 элементов.

Может кто-нибудь помочь мне с оптимальным решением.Этот алгоритм не подходит для обработки больших данных в массиве.

Answer 1

Как кто-то еще указал, что если у вас есть 10 ^ 18 чисел, это будет намного больше данных, чем вы можете вписать в память.Так что вам нужно потоковое решение.Вы также не хотите тратить много времени на выделение памяти или преобразование строк в символьные массивы, вызов функций для устранения дубликатов цифр и т. Д. В идеале вам нужно решение, которое просматривает каждый символ один раз.

Требуемый объем памяти программы ниже очень мал: всего два маленьких массива длинных целых чисел.

Разработанный мной алгоритм поддерживает два массива счетчиков на цифру.Один - это максимальное количество последовательных вхождений цифры, а другой - самое последнее число последовательных вхождений.

Код сам читает символ за символом, накапливая цифры, пока не встретит символ, которыйне является цифрой, то он обновляет массив текущих подсчетов для каждой встреченной цифры.Если текущий счет превышает максимальный счет, то максимальный счет для этой цифры обновляется.Если цифра не появляется в числе, ее текущий счетчик сбрасывается на 0.

Вхождение отдельных цифр в число поддерживается путем установки битов в переменной digits.Таким образом, число, такое как 1221, не будет считать цифры дважды.

using (var input = File.OpenText("filename"))
{
    var maxCounts = new long[]{0,0,0,0,0,0,0,0,0,0};
    var latestCounts = new long[]{0,0,0,0,0,0,0,0,0,0};
    char prevChar = ' ';

    word digits = 0;
    while (!input.EndOfStream)
    {
        var c = input.Read();

        // If the character is a digit, set the corresponding bit
        if (char.IsDigit(c))
        {
            digits |= (1 << (c-'0'));
            prevChar = c;
            continue;
        }

        // test here to prevent resetting counts when there are multiple non-digit
        // characters between numbers.
        if (!char.IsDigit(prevChar))
        {
            continue;
        }
        prevChar = c;

        // digits has a bit set for every digit
        // that occurred in the number.
        // Update the counts arrays.

        // For each of the first 10 bits, update the corresponding count.
        for (int i = 0; i < 10; ++i)
        {
            if ((digits & 1) == 1)
            {
                ++latestCounts[i];
                if (latestCounts[i] > maxCounts[i])
                {
                    maxCounts[i] = latestCounts[i];
                }
            }
            else
            {
                latestCounts[i] = 0;
            }
            // Shift the next bit into place.
            digits >> 1;
        }
        digits = 0;
    }
}

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

Answer 2

Все опубликованные ответы неверны, потому что все они проигнорировали самую важную часть вопроса:

Массив может содержать 10 ^ 18 элементов.

Этот массив читается с диска ?Предположим, каждый элемент составляет два байта, это два миллиона терабайтных дисков только для массива. Я не думаю, что это уместится в память. Вам придется использовать потоковое решение.

Сколько времени займет потоковое решение?Если вы можете обрабатывать миллиард элементов массива в секунду, что, по-видимому, в разумных пределах, вашей программе потребуется 32 года.

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

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

Answer 3

Конечно, не эффективное решение, но это будет работать.

public class Program
{
    public static int arrLength = 0;
    public static string[] arr;
    public static Dictionary<char, int> dct = new Dictionary<char, int>();

    public static void Main(string[] args)
    {
        dct.Add('0', 0);
        dct.Add('1', 0);
        dct.Add('2', 0);
        dct.Add('3', 0);
        dct.Add('4', 0);
        dct.Add('5', 0);
        dct.Add('6', 0);
        dct.Add('7', 0);
        dct.Add('8', 0);
        dct.Add('9', 0);

        arr = Console.ReadLine().Split(' ');
        arrLength = arr.Length;
        foreach (string str in arr)
        {
            char[] ch = str.ToCharArray();
            ch = ch.Distinct<char>().ToArray();
            foreach (char c in ch)
            {
                Exists(c, Array.IndexOf(arr, str));
            }
        }

        int val = dct.Values.Max();
        foreach(KeyValuePair<char,int> v in dct.Where(x => x.Value == val))
        {
            Console.WriteLine("Common digit {0} with frequency {1} ",v.Key,v.Value+1);
        }
        Console.ReadLine();
    }

    public static bool Exists(char c, int pos)
    {
        int count = 0;
        if (pos == arrLength - 1)
            return false;

        for (int i = pos; i < arrLength - 1; i++)
        {
            if (arr[i + 1].ToCharArray().Contains(c))
            {
                count++;
                if (count > dct[c])
                    dct[c] = count;
            }
            else
                break;
        }
        return true;
    }
}

Answer 4

Хорошо, я дам вам 3 версии

По сути, я просто загрузил список случайных целых чисел в виде строки, масштаб - сколько, и запустил его на Core и Framework, чтобы увидеть.Каждый тест проводился 10 раз и усреднялся.

Mine1

Использует различное

public unsafe class Mine : Benchmark<List<string>, char>
{
   protected override char InternalRun()
   {
      var result = new int[10];
      var asd = Input.Select(x => new string(x.Distinct().ToArray())).ToList();
      var raw = string.Join("", asd);

      fixed (char* pInput = raw)
      {
         var len = pInput + raw.Length;
         for (var p = pInput; p < len; p++)
         {
            result[*p - 48]++;
         }
      }

      return (char)(result.ToList().IndexOf(result.Max()) + '0');
   }
}

Mine2

В основном для обработки используется второй массив

public unsafe class Mine2 : Benchmark<List<string>, char>
{
   protected override char InternalRun()
   {
      var result = new int[10];
      var current = new int[10];
      var raw = string.Join(" ", Input);

      fixed (char* pInput = raw)
      {
         var len = pInput + raw.Length;
         for (var p = pInput; p < len; p++)
            if (*p != ' ')
               current[*p - 48] = 1;
            else
               for (var i = 0; i < 10; i++)
               {
                  result[i] += current[i];
                  current[i] = 0;
               }

      }

      return (char)(result.ToList().IndexOf(result.Max()) + '0');
   }
}

Mine3

Нет объединений или выделения строк

public unsafe class Mine3 : Benchmark<List<string>, char>
{
   protected override char InternalRun()
   {
      var result = new int[10];

      foreach (var item in Input)
         fixed (char* pInput = item)
         {
            var current = new int[10];
            var len = pInput + item.Length;

            for (var p = pInput; p < len; p++)
               current[*p - 48] = 1;

            for (var i = 0; i < 10; i++)
            {
               result[i] += current[i];
               current[i] = 0;
            }
         }


      return (char)(result.ToList().IndexOf(result.Max()) + '0');
   }
}

Результаты.Net Framework 4.7.1

Mode            : Release
Test Framework  : .Net Framework 4.7.1
Benchmarks runs : 10 times (averaged)

Scale : 10,000
Name     |   Average |   Fastest | StDv |     Cycles | Pass |        Gain
--------------------------------------------------------------------------
Mine3    |  0.533 ms |  0.431 ms | 0.10 |  1,751,372 | Base |      0.00 %
Mine2    |  0.994 ms |  0.773 ms | 0.38 |  3,100,896 | Yes  |    -86.63 %
Mine     |  8.122 ms |  7.012 ms | 1.29 | 27,480,083 | Yes  | -1,424.78 %
Original | 20.729 ms | 16.044 ms | 4.56 | 65,316,558 | No   | -3,791.47 %


Scale : 100,000
Name     |    Average |    Fastest |  StDv |      Cycles | Pass |        Gain
------------------------------------------------------------------------------
Mine3    |   4.766 ms |   4.475 ms |  0.34 |  16,140,716 | Base |      0.00 %
Mine2    |   8.424 ms |   7.890 ms |  0.33 |  28,577,416 | Yes  |    -76.76 %
Mine     |  96.650 ms |  93.066 ms |  3.35 | 327,615,266 | Yes  | -1,927.94 %
Original | 163.342 ms | 154.070 ms | 12.61 | 550,038,934 | No   | -3,327.32 %


Scale : 1,000,000
Name     |      Average |      Fastest |  StDv |        Cycles | Pass |        Gain
------------------------------------------------------------------------------------
Mine3    |    49.827 ms |    48.600 ms |  1.19 |   169,162,589 | Base |      0.00 %
Mine2    |   106.334 ms |    97.641 ms |  6.53 |   359,773,719 | Yes  |   -113.41 %
Mine     | 1,051.600 ms | 1,000.731 ms | 35.75 | 3,511,515,189 | Yes  | -2,010.51 %
Original | 1,640.385 ms | 1,588.431 ms | 65.50 | 5,538,915,638 | No   | -3,192.18 %

Результаты .Net Core 2.0

Mode            : Release
Test Framework  : Core 2.0
Benchmarks runs : 10 times (averaged)

Scale : 10,000
Name     |   Average |   Fastest | StDv |     Cycles | Pass |        Gain
--------------------------------------------------------------------------
Mine3    |  0.476 ms |  0.353 ms | 0.12 |  1,545,995 | Base |      0.00 %
Mine2    |  0.554 ms |  0.551 ms | 0.00 |  1,883,570 | Yes  |    -16.23 %
Mine     |  7.585 ms |  5.875 ms | 1.27 | 25,580,339 | Yes  | -1,492.28 %
Original | 21.380 ms | 16.263 ms | 6.46 | 65,741,909 | No   | -4,388.14 %


Scale : 100,000
Name     |    Average |    Fastest |  StDv |      Cycles | Pass |        Gain
------------------------------------------------------------------------------
Mine3    |   3.946 ms |   3.685 ms |  0.25 |  13,409,181 | Base |      0.00 %
Mine2    |   6.203 ms |   5.796 ms |  0.33 |  21,042,340 | Yes  |    -57.21 %
Mine     |  72.975 ms |  68.599 ms |  4.13 | 246,471,960 | Yes  | -1,749.41 %
Original | 161.400 ms | 145.664 ms | 19.37 | 544,703,761 | Yes  | -3,990.40 %


Scale : 1,000,000
Name     |      Average |      Fastest |  StDv |        Cycles | Pass |        Gain
------------------------------------------------------------------------------------
Mine3    |    41.036 ms |    38.928 ms |  2.47 |   139,045,736 | Base |      0.00 %
Mine2    |    71.283 ms |    68.777 ms |  2.49 |   241,525,269 | Yes  |    -73.71 %
Mine     |   749.250 ms |   720.809 ms | 27.79 | 2,479,171,863 | Yes  | -1,725.84 %
Original | 1,517.240 ms | 1,477.321 ms | 48.94 | 5,142,422,700 | No   | -3,597.35 %

Сводка

Распределение строк, объединение и различный отстой для производительности.Если вам нужно больше производительности, вы можете разбить список на рабочие нагрузки и разбить его параллельно

Answer 5

Я не использовал массивы, я не уверен, если вы должны использовать массивы, если нет, проверьте это решение.

static void Main(string[] args)
    {
        List<char> numbers = new List<char>();
        Dictionary<char, int> dct = new Dictionary<char, int>()
        {
            { '0',0 },
            { '1',0 },
            { '2',0 },
            { '3',0 },
            { '4',0 },
            { '5',0 },
            { '6',0 },
            { '7',0 },
            { '8',0 },
            { '9',0 },
        };

        string option;

        do
        {
            Console.Write("Enter number: ");
            string number = Console.ReadLine();
            numbers.AddRange(number);

            Console.Write("Enter 'X' if u want to finish work: ");
            option = Console.ReadLine();

        } while (option.ToLower() != "x");

        foreach(char c in numbers)
        {
            if(dct.ContainsKey(c))
            {
                dct[c]++;
            }
        }

        foreach(var keyValue in dct)
        {
            Console.WriteLine($"Char {keyValue.Key} was used {keyValue.Value} times");
        }

        Console.ReadKey(true);
    }

Answer 6

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

12 23 231 -> "1223231", цикли посчитай.

Это должно быть достаточно быстро O (n) и требовать только 10 записей в вашем словаре.Насколько «быстро» вам точно нужно?