Помогите написать алгоритм сравнения

Ачат прошу помощи
Нам даны два строковых массива, в строках восьмизначные числа. первый массив 100 млн значений второй массив 10 000 значений. Нужно сравнить каждую строку из второго массива с каждой строкой из первого и при наличии отличий удалить строку из второго массива.
Надеюсь задача понятна, очень нужно ребят, благодарен буду!
ЯП не важен

 

както калечно ты написал, ну если я правильно тебя понял и тебе ножно вывести из массива2 то что есть в массиве1( при наличии отличий удалить строку из второго массива)

PHP:

<?php
$arrat_one = array(1234,2376896745,34523,352768345,2345);
$arrat_two = array(1234,2345,3786974523,352345);
$arrat_three = array();

foreach( $arrat_two as $at )  {

if( in_array( $at , $arrat_one) ) {

    $arrat_three[] = $at;                                      
                                  }
                                                }

print_r($arrat_three);

?>

 

не совсем, при наличии определенного кол-ва отличий. тоесть если между строкой 1 и 2 у нас 3 отличия то строка отсеивается. а если менее то остается.

Основная проблема это скорость мой алгоритм будет месяц считать эти варианты....

 

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

 

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

 

Можно еще отсортировать оба массива, и сохранять позицию в большем массиве после каждого сравнения.

 

Собственно, сам алгоритм (дабы мозгом и ты поработал - допили )

c#

Code:

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace csharpSpeed
{
    class Program
    {
        private static List<string> readLinesRange(string file, int begin, int end)
        {
            List<string> res = new List<string>();
            int line = 0;

            using (StreamReader sr = new StreamReader(file))
            {

                while (line <  begin)
                {
                    sr.ReadLine();
                    line++;
                }

                while (line < end)
                {
                    res.Add(sr.ReadLine());
                    line++;
                }
                sr.Close();
            }

            return res;
        }

        static void Main(string[] args)
        {
            DateTime begin_time = DateTime.Now;
            int bigLines = 1000000; //всего строк в большем списке
            int smallLines = 100; //всего строк в меньшем списке
            int step = 10000; //шаг (для большого списка).. т.е. по 10000 строк за проход цикла
            List<string> bigList = new List<string>();
            List<string> smallList = readLinesRange("e:\\out_small.txt", 0, smallLines); //всего строк в меньшем списке


            //с какой линии считать следующий диапазон линий ?
            int last = 0;

            for (int a = 1; a <= bigLines / step; a++)
            {
                bigList = readLinesRange("e:\\out.txt", last, step * a);

                //сделующее начало диапазона = текущие начало диапазона + шаг
                last += step;


                //сравнение тут... собственно, тут делай проверки с меньшим списком



                //очистить буффер после проведения сравнений
                 bigList.Clear();
                GC.Collect();
            }

            Console.WriteLine("Done !");
            TimeSpan end_time = (DateTime.Now - begin_time);
            Console.WriteLine("Done in h{0}:m{1}:s{2}:ms{3} ", end_time.Hours, end_time.Minutes, end_time.Seconds, end_time.Milliseconds);
            Console.ReadKey();
        }
    }
}

Файл с 1000000 строками за 3.5 секунды в буффер по 10 000 линий. Собственно от тебя требуется только замутить вложенный цикл для сравнения с меньшим списком строк... Не думаю что это потребует слишком много усилий... Сам алгоритм, думаю, ясен. Брать в диапазоны и сравнивать, ибо это огромный выигрыш в скорости. Однако, чем больше раз мы проходим цикл (т.е. чем шаг меньше), тем производительность считывания из файла меньше (т.к. приходится записывать строки в список опять и опять)...