0

Есть один файл (txt). В нем записаны номера карт (1 800 000 шт.).

пример:

000001000001097
000001000001213
000001000001268
000001000001291
000001000001365
000001000001376
000001000001398

Задача:

Нужно проверить есть ли такой номер карты который был введен. И проверить быстро! Проверяться будет часто из одного запуска програмы.

Что я уже написал:

StreamReader str = new StreamReader("Blacklist.txt", Encoding.Default);
            while (!str.EndOfStream)
            {
                string st = str.ReadLine();
                if (st.StartsWith(tb_cardinput.Text))
                {
                    textBox1.Text = st;
                    break;// останавливаем цикл
                }
            }
            str.Close();

Вопрос

Мне кажется что это должно быть написано не так. Ведь как мне кажется было бы лучше например один раз загрузить весь файл в переменную и в ней искать или в массив. Как лучше сделать в этой ситуации? А главное чтобы искало быстро?

Проблема

Почему код что я написал всегда возвращает первую строку!

P.S.

Я в C# новенький (1 неделя). Поделитесь пожалуста советами и если есть примерами) а так C# очень нравится!

3 ответа 3

7
var cardsNumbers = File.ReadAllLines("Blacklist.txt");
var LogHashSet = new HashSet<string>(cardsNumbers);

bool isExist = LogHashSet.Contains("000001000001365");

Пишут, что по HashSet поиск самый быстрый.

Переменную LogHashSet храните в классе и каждый раз вызывайте метод Contains.

UPD: @DreamChild предложил использовать бинарный поиск (сам сначала думал так предложить). Чтобы не быть голословным, решил сделать тесты (тесты проводился на 10 миллионах чисел).


Тест первый - в качестве массива для хранения номеров карт string[]:

Время создания массива cardsNumbers - 3 секунды

Памяти необходимо под массив cardsNumbers - 544 мегабайт

  • HashSet

Время поиска - 15 Ticks т.е. 1,5 микросекунды

Необходимо памяти - 156 мегабайт

  • BinarySearch

Время поиска - 1018 Ticks при не сортированном массиве и 512 Ticks при сортированном. Этот момент странен тем, что массив я отдаю сортированный, но вызов метода Sort увеличивает скорость поиска в 2 раза. Возможно, массив располагается каким-то образом в памяти.

Вызов метода Sort - 36 секунд (вызов делается 1 раз, но подождать придётся)

Необходимо памяти - 39 мегабайт.


Тест второй - в качестве массива для хранения номеров карт int[]:

Время создания массива cardsNumbers - 6~8 секунд

Памяти необходимо под массив cardsNumbers - 47 мегабайт

  • HashSet

Время поиска - 100~200 Ticks

Необходимо памяти - 156 мегабайт

  • BinarySearch

Время поиска - 400~500 Ticks. Теперь уже вызов метода Sort не даёт увеличения скорости поиска.

Необходимо памяти - 39 мегабайт.


Вывод:

Создавая массив int:

Плюсы:

  • мы экономим 497 мегабайт;
  • нет необходимости сортировать массив для бинарного поиска (экономим 36 секунд на старте приложения);
  • бинарный поиск по сортированному массиву почти эквивалентен поиску по int массиву;

Минусы:

  • теряем при старте приложения 3~5 секунд;
  • скорость поиска HashSet уменьшается в 10 раз.

Создавая массив string:

Плюсы:

  • имеем самую высокую скорость поиска - 15 Ticks = 1,5 микросекунды;

Минусы:

  • под массив cardsNumbers необходимо 544 мегабайт памяти.

Итак:

  • если у Вас достаточно памяти, то используйте HashSet и храните cardsNumbers в массиве String[];
  • если у Вас мало памяти, то используйте обычный List и бинарный поиск, а cardsNumbers храните в int[] массиве.

UPD2 Пример кода:

using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var cards = new Cards();
            Console.WriteLine(cards.Contains("000001000001365"));
        }
    }
}

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

namespace ConsoleApplication1
{
    class Cards
    {
        private const string PATH_TO_FILE = "Blacklist.txt";
        private HashSet<string> cardsNumbers;

        public Cards()
        {
            var cardsNumbersFromFile = File.ReadAllLines(PATH_TO_FILE);
            cardsNumbers = new HashSet<string>(cardsNumbersFromFile);
        }

        public bool Contains(string value)
        {
            return cardsNumbers.Contains(value);
        }
    }
}
3
  • Спасибо! ваш пример работает! У меня есть еще вопрос... как мне записать: var LogHashSet = new HashSet<string>(cardsNumbers); в свой клас? (например test1). Когда пишу: public var cardNumbersLogHash { get; set; } ошибка с var. Если вместо var - object то проблема потом с методом Contains
    – Mike
    Commented 12 окт. 2013 в 11:14
  • Отличный ответ!
    – Mike
    Commented 12 окт. 2013 в 11:20
  • Вы можете ускорить работу, пользуясь File.ReadLines вместо File.ReadAllLines.
    – VladD
    Commented 12 окт. 2013 в 19:59
3

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

8
  • Бинарный поиск по идее быстрее: не надо читать весь файл в память. (Для одного искомого элемента.)
    – VladD
    Commented 12 окт. 2013 в 19:52
  • @VladD Бинарный поиск на диске? Могет быть, могет быть. Только я в современных файловых системах слабо ориентируюсь. Если можно найти хвост файла не просматривая его, то да. Опять же для одиночного поиска. При массовом он всё равно окажется в кеше.
    – alexlz
    Commented 12 окт. 2013 в 20:43
  • 1
    @alexlz: размер строки одинаков, такшта начало каждой строки расположено по фиксированному смещению. Ну и файлы на Вендах вполне себе произвольного доступа (а до-диез скорее всего обозначает именно форточки, а не Моно). Это, конечно, всё так, если размер кластера сильно меньше размера файла, и если мы и правда получим выигрыш, не загружая весь файл в память. --- Для массового поиска, понятно, лучше всего предобработка (то есть HashSet<int>).
    – VladD
    Commented 12 окт. 2013 в 20:47
  • @VladD фиксированный размер строки избавляет от необходимости искать начало/конец строки. А вот как стандартными вызовами определить смещение конца файла (в смысле ftell). Не читая файл целиком. Может и несложно, но искать лениво. Так что секрет -- в студию
    – alexlz
    Commented 12 окт. 2013 в 21:01
  • @alexlz: например, FileStream.Length (размер) и FileStream.Position (установка в нужную позицию). Вот подтверждение того, что Length не требует предварительного чтения файла: stackoverflow.com/q/9178681/276994 (Вы думаете, что виндушный file manager, показывая размеры файлов, читает их полностью?)
    – VladD
    Commented 12 окт. 2013 в 21:34
1

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

Ну так создайте массив типа string и в цикле заполните его значениями из str.

Почему код что я написал всегда возвращает первую строку!

Мне кажется что это

if (st.StartsWith(tb_cardinput.Text))

Лучше заменить на это:

if (st === (tb_cardinput.Text))

Ибо StartSwitch делает так: Определяет, совпадает ли начало данного экземпляра строки с указанной строкой

Сам C# второй день изучаю.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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