1

Есть 2 строковых массива с большим количеством строк.

string[] words1;
string[] words2;

Если в этих двух массивах находится совпадение по заданному мной условию, нужно оба элемента добавить в разные листы/массивы. Примерный код:

            List<string> russian = new List<string>();
            sr = new StreamReader(@"russian.txt");//1 строка=1 слово русского языка
            while(!sr.EndOfStream)
            {
                russian.Add(sr.ReadLine());
            }//примерно 1.5 миллиона строк
            int[] qw = { -1 };//индексы, которые надо игнорировать, сейчас не используется
            var a = russian.Where(q => q.Length == 8);//отсеиваем все слова с 8 буквами
            var b = a.Where(q => Check(q, qw));//отсеиваем слова с повторяющимися буквами
            var a1 = russian.Where(q => q.Length == 7);//отсеиваем все слова с 7 буквами
            var b1 = a1.Where(q => Check(q, qw));//отсеиваем слова с повторяющимися буквами
            string[] word1 = b.ToArray();//46к строк
            string[] word2 = b1.ToArray();//43к строк
            List<string> word11 = new List<string>();
            List<string> word22 = new List<string>();
            for(int i=0;i<word1.Length;i++)
            {
                for(int j=i+1; j<word2.Length;j++)
                {
                    if(word1[i][0]==word2[j][0]&& word1[i][4] == word2[j][2] && word1[i][7] == word2[j][6])
                    {
                        if (!word11.Exists(q => q.Equals(word1[i])))
                            word11.Add(word1[i]);
                        if (!word22.Exists(q => q.Equals(word2[j])))
                            word22.Add(word2[j]);
                    }
                    Console.WriteLine(i + " " + j);
                }
            }
        static bool Check(string str,int[] ind)//проверяет, имеет ли строка повторяющиеся символы, int[] ind - игнорируемые индексы
        {
            bool q=true;
            string a = "";
            int t=0;
            for(int i=0;i<str.Length;i++)
            {
                if (i != ind[t])
                    a += str[i];
                else
                {
                    i++;t++;
                }
            }
            for (int i = 0; i < a.Length; i++)
            {
                for (int j=i+1;j<a.Length;j++)
                {
                    if (a[i] == a[j])
                        q = false;
                }
            }
            return q;
        }

Но в лучшем случае он будет выполняться целые сутки.
Как с помощью linq выполнить этот же код?
UPD:
Вот пример попроще:

            string[] a1 = { "apple", "nilmar", "anpsa" };
            string[] a2 = { "ars", "aep", "fff", "arp" };

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

            List<string> word1 = new List<string>();
            List<string> word2 = new List<string>();

Где в первом будут лежать "apple" и "anpsa", а во втором "aep" и "arp"

14
  • Есть ощущение, что для вашего примера linq только еще больше замедлит выполнение.
    – Talleyran
    1 апр 2021 в 5:55
  • А Какого типа условие? 1 апр 2021 в 6:22
  • 1
    Здесь требуется не переход к linq, а уход от полного перебора элементов - он имеет сложность O(N^2), использовать не массивы, а хеш таблицы.
    – A K
    1 апр 2021 в 6:23
  • 1
    @AzizUmarov добавил пример
    – OLIMP
    1 апр 2021 в 6:41
  • 1
    @aepot добавил код метода
    – OLIMP
    1 апр 2021 в 7:51

1 ответ 1

1

Попробовал немного оптимизировать

static void Main(string[] args)
{
    int[] qw = Array.Empty<int>();

    List<string> words1 = new List<string>();
    List<string> words2 = new List<string>();
    using (var sr = new StreamReader("russian.txt"))
    {
        while (!sr.EndOfStream)
        {
            string word = sr.ReadLine();
            if (word.Length == 8 && Check(word, qw))
                words1.Add(word);
            else if (word.Length == 7 && Check(word, qw))
                words2.Add(word);
        }
    }
    // для контроля уникальности используем специально оптимизированные для этого коллекции
    HashSet<string> result1 = new HashSet<string>();
    HashSet<string> result2 = new HashSet<string>();

    for (int i = 0; i < words1.Count; i++)
    {
        string w1 = words1[i]; // кешируем ссылку на строку, чтобы не обращаться много раз через индекс
        for (int j = i + 1; j < words2.Count; j++)
        {
            string w2 = words2[j];
            if (w1[0] == w2[0] && w1[4] == w2[2] && w1[7] == w2[6])
            {                        
                result1.Add(w1);
                result2.Add(w2);
            }
        }
    }

    File.WriteAllLines("words1.txt", result1);
    File.WriteAllLines("words2.txt", result2);
    Console.ReadKey();
}

// индексы должны быть уникальны и отсортированы по возрастанию
// если нет индеков для исключения, массив индексов должен быть пустым
static bool Check(string str, int[] indexes) 
{
    string word = str.ToLower();
    if (indexes.Length == 0)
        return word.Distinct().Count() == word.Length;

    HashSet<char> distinct = new HashSet<char>();
    int i = 0;
    while (true)
    {
        while (Array.BinarySearch(indexes, i) >= 0)
            i++;
        if (i == word.Length)
            break;
        if (!distinct.Add(word[i++]))
            return false.
    }
    return true;
}

Если у вас так быстро выполняется, не могли бы, пожалуйста, добавить третье слово из 6 букв с условием w1[0] == w2[0] && w1[4] == w2[2] && w1[7] == w2[6]&& w3[1] == w2[1] && w3[3] == w1[3] && w3[4] == w2[2] && w3[4] == w1[4] и скинуть результаты?

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

static async Task Main(string[] args)
{
    int[] qw = Array.Empty<int>();

    List<string> words1 = new List<string>();
    List<string> words2 = new List<string>();
    List<string> words3 = new List<string>();
    using (var sr1 = new StreamReader("russian.txt"))
    {
        while (!sr1.EndOfStream)
        {
            string word = sr1.ReadLine();
            if (word.Length == 8 && Check(word, qw))
                words1.Add(word);
            else if (word.Length == 7 && Check(word, qw))
                words2.Add(word);
            else if (word.Length == 6 && Check(word, qw))
                words3.Add(word);
        }
    }

    Console.WriteLine(string.Join(" ", words1.Count, words2.Count, words3.Count));

    HashSet<string> result1 = new HashSet<string>();
    HashSet<string> result2 = new HashSet<string>();
    HashSet<string> result3 = new HashSet<string>();

    using SemaphoreSlim semaphore = new SemaphoreSlim(Environment.ProcessorCount * 2);
    List<Task> tasks = new List<Task>();
    for (int i = 0; i < words1.Count; i++)
    {
        await semaphore.WaitAsync();
        Console.Write(i + " ");
        string w1 = words1[i];
        int ii = i;
        tasks.Add(Task.Run(() =>
        {
            for (int j = ii + 1; j < words2.Count; j++)
            {
                string w2 = words2[j];
                for (int k = j + 1; k < words3.Count; k++)
                {
                    string w3 = words3[k];
                    if (w1[0] == w2[0] && w1[4] == w2[2] && w1[7] == w2[6] && w3[1] == w2[1] && w3[3] == w1[3] && w3[4] == w2[2] && w3[4] == w1[4])
                    {
                        lock (result1) result1.Add(w1);
                        lock (result2) result2.Add(w2);
                        lock (result3) result3.Add(w3);
                    }
                }
            }
            semaphore.Release();
        }));
    }
    await Task.WhenAll(tasks);
    Console.WriteLine(string.Join(" ", result1.Count, result2.Count, result3.Count));

    File.WriteAllLines("words1.txt", result1);
    File.WriteAllLines("words2.txt", result2);
    File.WriteAllLines("words3.txt", result3);
    Console.WriteLine("Done.");
    Console.ReadKey();
}

Добавил Console.Write во внешнем цикле, чтобы отслеживать позицию.

24
  • Если медленно, можно попробовать свести к одной вычитке файла вместо двух.
    – aepot
    1 апр 2021 в 9:13
  • 1
    Считывается то все шустренько, фор лупы все время забирают. 46к*43к, как-никак. Запустил программу на vps - раз в 5 быстрее работает, чем у меня
    – OLIMP
    1 апр 2021 в 9:41
  • 1
    @AK Я бы сразу задал в половину от words.Count там если и будет прирост, то совсем незначительный, потому что по факту внутрь if с добавлением оно попадает кака я понял, не часто. Просто лярд проверок с выдергиванием 6 символов по индексу из 2 строк (6 лярдов обращений к индексаторам) - это тормоза. Возможно здесь unsafe прокатит, но я за грамотное распараллеливание как минимум по количеству ядер Environment.ProcessorsCount, хотя можно и то и другое сразу.
    – aepot
    1 апр 2021 в 10:50
  • 1
    Если у вас так быстро выполняется, не могли бы, пожалуйста, добавить третье слово из 6 букв с условием w1[0] == w2[0] && w1[4] == w2[2] && w1[7] == w2[6]&& w3[1] == w2[1] && w3[3] == w1[3] && w3[4] == w2[2] && w3[4] == w1[4] и скинуть результаты?
    – OLIMP
    1 апр 2021 в 11:34
  • 1
    @OLIMP в любом случае в 3 уровня вложенности выполняется очень долго. Я распараллелил код, он работает на всех ядрах процессора, но даже несмотря на то что я собрал релизную версию, все равно это долго. Чуть позже опубликую полную версию в ответе. Вот пока я пишу этот коммент оно обработало 1000 позиций из внешнего цикла.
    – aepot
    1 апр 2021 в 12:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.