Здравствуйте, trotski, Вы писали:

T> Я ищу работу C# стажера, и мне предложили выполнить тестовое задание.

Нда... тесты на стажера — это уже клиника.

А многопоточность для поиска по фйлам да еще и для стажера — это просто бред.

Или от тебя хотели избавиться, или хорошо, что ты в эту контору не попал.

Здравствуйте, vitaly_spb, Вы писали:

GZ>>Сомневаюсь что они имели ввиду просто открытие второго потока вначале. Скорее многопоточность касалась операции поиска значения.
_>странно оно как-то, но звучит действительно как будто надо для подкаталогов по потоку создать
Судя по постановке, наиболее эффективным приложением многопоточности будет поиск текста для каждого файла в отдельном потоке. И вероятней всего, через очередь потоков.

Здравствуйте, trotski, Вы писали:

Честно говоря, страшно даже на твой код смотреть. Зачем так наворачивать-то? И на фига тебе мьютексы тут дались? Все это значительно проще делается. Типа такого (не компилил но должно работать):

using System;
using System.IO;
using System.Threading;

class Program
{
    delegate void SearchCallBack(DirectoryInfo dir, string searchString);

    static void Main(params string[] args)
    {
        IAsyncResult res = ((SearchCallBack)ScanDirectory).
            BeginInvoke(new DirectoryInfo("C:\\projects"), "Namespace", null, null);
        res.AsyncWaitHandle.WaitOne();
    }
        
    static void ScanDirectory(DirectoryInfo dir, string searchString)
    {        
        foreach (FileSystemInfo fi in dir.GetFileSystemInfos())
            if (fi is DirectoryInfo)
                ScanDirectory(fi as DirectoryInfo, searchString);
            else
            {
                try
                {
                    ScanFile(fi.FullName, searchString);
                }
                catch (IOException)
                {
                    Console.WriteLine("Unable to open file '{0}'", fi.FullName);
                }
            }
    }
    
    
    static void ScanFile(string fileName, string searchString)
    {
        using (StreamReader sr = File.OpenText(fileName))
        {
            string line = null;
        
            while ((line = sr.ReadLine()) != null)
            {
                int index = -1;
                if ((index = line.IndexOf(searchString)) != -1)
                    Console.WriteLine("Found in '{0}' at pos {1}", fileName, index);
            }
        }
    }
}

Кстати
А какие пожелания по поводу работы? Интересует именно C#? (из .NET)

ВВ>Вариант из 5 строк прогоняется 200 тыс. раз.

Интересно сравнить QuickSort и пузерек таким образом. Почему-то мне кажется, что пузырек порвет

Здравствуйте, помогите, пожалуйста, найти красивое решение. Я ищу работу C# стажера, и мне предложили выполнить тестовое задание. Я его с треском провалил. Но дело не в этом, я просто хочу узнать, как такое задание делают нормальные программисты. Хочу научится. Опыта нет, а желание работать есть.
Вот текст задания:
Создать приложение, ищущее текст в файлах, находящихся в указанном каталоге и его подкаталогах. Приложение должно использовать многозадачность. Можно сделать его консольным.
А вот мое решение:
Main.cs

using System;
using System.IO;
using System.Text;

namespace FindText
{

    public class App
    {
        
    
        public static void Main(string[] args)
        {
            //Если программа запущена без аргументов или каталог задан,
            //а строка нет, то информируем о параметрах запуска и выходим            
            if((args.Length < 1)||(args.Length < 3 && args[0] == "-d"))
            {
                PrintInfo();
                return;
            }
            
            //Получаем текущий каталог на случай, если в опциях не будет задан другой
            string dir = Directory.GetCurrentDirectory();

            //Считаем, что каталог не задан, а значит текст для поиска идет с нулевого
            //элемента массива аргументов
            int textBegining = 0;                
            StringBuilder text = new StringBuilder();
            
                        
            //Задан ли каталог?
            if(args[0] == "-d")
            {
                dir = args[1];
                //Задан существующий каталог?
                if(!Directory.Exists(dir))
                {
                    Console.WriteLine("Directory does not exists");
                    return;
                }
                //Текст в массиве аргументов идет со второй позиции
                textBegining = 2;
                        
            }
            
            //Получаем строку для поиска путем слияния всех аргументов,
            //не относящихся к каталогу
            for(int i = textBegining; i < args.Length; i++)
            {
                text.Append(args[i]);
            }
    
            //Вызываем статический метод поиска
            TextFinder.Find(dir, text.ToString());
            Console.WriteLine("OK");
            
            return;
        }
        
        private static void PrintInfo()
        {
                Console.WriteLine("findtext. Test job. Vladimir V Davydov. 2005");
                Console.WriteLine("Usage: findtext [-d directory] \"text to find\"");
        }
    }

}

TextFinder.cs

/*
 * Created by SharpDevelop.
 * User: admin
 * Date: 10.02.2006
 * Time: 17:54
 * 
 * To change this template use Tools | Options | Coding | Edit Standard Headers.
 */

using System;
using System.IO;
using System.Collections;
using System.Threading;

namespace FindText
{
    /// <summary>
    /// Класс, осуществляющий поиск в каталоге.
    /// </summary>
    public class TextFinder
    {
        //Счетчик запущенных потоков, обрабатывающих каталоги
        private static uint _directoryThreadCounter;
        //Счетчик запущенных потоков, обрабатывающих файлы
        private static uint _fileThreadCounter;
        
        //Мьютекс для работы с очередью каталогов
        private static Mutex _dirMutex;
        //Мьютекс для работы с очередью файлов
        private static Mutex _fileMutex;
        //Мьютекс для работы со счетчиком каталогов
        private static Mutex _dirCounterMutex;
        //Мьютекс для работы со счетчиком файлов
        private static Mutex _fileCounterMutex;
        
        //Очередь каталогов для обработки
        private static Queue _dirFIFO;
        //Очередь файлов для обработки
        private static Queue _fileFIFO;
        
        //Текст для поиска
        private static string _text;
        
        
        /// <summary>
        /// Конструктор
        /// </summary>
        /// <remarks>
        /// Конструктор спрятал от греха подальше, 
        /// т.к. будет вызывать только один статический метод
        ///</remarks>
        private TextFinder()
        {
            
        }
        
        ///<summary>Функция потока обработки каталогов</summary>                
        private static void DirProc(object data)
        {
            string currentDir;
            //Пытаемся получить имя каталога из переданного потоку объекта
            try
            {
                currentDir = (string)data;
            }
            catch(InvalidCastException)
            {
                //Производим захват мьютекса для работы со счетчиком потоков
                _dirCounterMutex.WaitOne();
                //Закончили работу и себя за поток уже не считаем ;)
                _directoryThreadCounter--;
                _dirCounterMutex.ReleaseMutex();
                
                return;
            }
            
            
            //Console.WriteLine("Processing directory " + currentDir);
            
            //получаем список подкаталогов в текущем каталоге
            string [] subDirectories = Directory.GetDirectories(currentDir);
            
            //производим захват мьютекса для работы с очередью подкаталогов
            _dirMutex.WaitOne();           
            //добавляем в очередь подкаталоги
            foreach(string dir in subDirectories)
            {
                    _dirFIFO.Enqueue(dir);
            } 
            //Высвобождаем мьютекс
            _dirMutex.ReleaseMutex();
            
            //получаем список файлов в текущем каталоге
            string [] files = Directory.GetFiles(currentDir);
            
            //производим захват мьютекса для работы с очередью файлов
            _fileMutex.WaitOne();
            //Добавляем в очередь обработки файлы
            foreach(string fileName in files)
            {            
                _fileFIFO.Enqueue(fileName);
            }             
            _fileMutex.ReleaseMutex();
            
            //Производим захват мьютекса для работы со счетчиком потоков
            _dirCounterMutex.WaitOne();
            //Закончили работу и себя за поток уже не считаем ;)
            _directoryThreadCounter--;
            _dirCounterMutex.ReleaseMutex();
            return;
        }
        /// <summary>
        /// Функция потока обработки файлов
        /// </summary>
        /// <param name="data"></param>
        private static void FileProc(object data)
        {
            string line;
            string file;
            
            
            //Получаем имя файла из переданного объекта
            try
            {
                 file = (string)data;
            }
            catch(InvalidCastException)
            {
                _fileCounterMutex.WaitOne();
                _fileThreadCounter--;
                _fileCounterMutex.ReleaseMutex();
                return;
            }
            
            
            //Console.WriteLine("Processing file " + file);
            
            #region Сам поиск
            try
            {
                //Если ищем текст, и все файлы рассматриваем как текстовые,
                //то должно быть что-то подобное
                using(StreamReader rs = new StreamReader(file))
                {
                     while ((line = rs.ReadLine()) != null) 
                     {
                         if(line.IndexOf(_text) != -1)
                             Console.WriteLine("Text founded in " + file);
                     }
                    
                }
            }
            catch
            {
                _fileCounterMutex.WaitOne();
                _fileThreadCounter--;
                _fileCounterMutex.ReleaseMutex();
                return;
            }
            #endregion Сам поиск

            //Выходим из потока, а перед выходом уменьшаем кол-во ссылок
            _fileCounterMutex.WaitOne();
            _fileThreadCounter--;
            _fileCounterMutex.ReleaseMutex();
            return;
        }
        
        public static void Find(string directory, string text)
        {
            //Создаем очереди
            _dirFIFO = new Queue();
            _fileFIFO = new Queue();
            
            //Создаем мьютексы
            _dirMutex = new Mutex();
            _fileMutex = new Mutex();
            
            _dirCounterMutex = new Mutex();
            _fileCounterMutex = new Mutex();
            
            _text = text;
            
            //Помещаем в очередь каталогов стартовый
            _dirFIFO.Enqueue(directory);
            
            
            uint dirCount = 0;
            uint fileCount = 0;
            
            string dir = string.Empty;
            string file = string.Empty;
            
            do
            {
                _dirMutex.WaitOne();
                //Смотрим, как там поживает наша очередь
                if(_dirFIFO.Count > 0)
                {
                    //Если в ней есть, что обрабатывать,
                    //то извлекаем элемент
                    dir = (string)_dirFIFO.Dequeue();
                    _dirCounterMutex.WaitOne();                                                
                    ++_directoryThreadCounter;
                    _dirCounterMutex.ReleaseMutex();
                }
                else
                    dir = string.Empty;
                
                _dirMutex.ReleaseMutex();
                
                //Добавляем в пул потоков поток для выбранного каталога
                if(dir != string.Empty)
                    ThreadPool.QueueUserWorkItem(new WaitCallback(DirProc), dir);
                
                
                
                _fileMutex.WaitOne();
                //То же, что и с каталогами, пока очередь не пуста, 
                //обрабатываем очередь, извлекая файлы и добавляя в
                //пул потоков вызов
                if(_fileFIFO.Count > 0)
                {
                    file = (string)_fileFIFO.Dequeue();
                    _fileCounterMutex.WaitOne();                                                
                    ++_fileThreadCounter;
                    _fileCounterMutex.ReleaseMutex();
                }
                else
                    file = string.Empty;
                
                _fileMutex.ReleaseMutex();
                
                if(file != string.Empty)
                    ThreadPool.QueueUserWorkItem(new WaitCallback(FileProc), file);
                
                //Получаем кол-во запущенных потоков, обрабатывающих каталоги
                _dirCounterMutex.WaitOne();                
                dirCount = _directoryThreadCounter;                    
                _dirCounterMutex.ReleaseMutex();                
                
                //Получаем кол-во запущенных потоков, обрабатывающих файлы
                _fileCounterMutex.WaitOne();
                fileCount = _fileThreadCounter;                    
                _fileCounterMutex.ReleaseMutex();
                
                //Заснем (~ 40 мс)
                Thread.Sleep(0);
                
                //Если хоть один поток еще жив, ждем его
            }while(dirCount > 0 || fileCount > 0);
            
            
        }
        
    }
}

Дополнительные "ненужные" счетчики и связанная с ними задержка возникли по причине того, что в .NET Framework 1.1 глюк с заврешением работы приложения: если поток из пула с установленным IsBackground в false завершается позже потока, его в пул поместившего, приложение зависает. Я с этим столкнулся при выполнении задания. Пришлось искусственно порождающий поток останавливать.

Как все это сделать правильней и элегантней? Научите идиота.

Глюки обычно не в .net, а совсем в другом месте.
IsBackground = true

Имхо ScanDirectory лучше сделать так:

    static void ScanDirectory(DirectoryInfo dir, string searchString)
    {
        ArrayList waitHandles = new ArrayList();
        foreach (FileSystemInfo fi in dir.GetFileSystemInfos())
            if (fi is DirectoryInfo)
                waitHandles.Add(
                    new DirScanDelegate(ScanDirectory).
                    BeginInvoke(fi as DirectoryInfo, searchString, null, null).AsyncWaitHandle
                );
            else
            {
                try
                {
                    ScanFile(fi.FullName, searchString);
                }
                catch (IOException)
                {
                    Console.WriteLine("Unable to open file '{0}'", fi.FullName);
                }
            }
        WaitHandle.WaitAll((WaitHandle[]) waitHandles.ToArray(typeof (WaitHandle)));
    }

Здравствуйте, Воронков Василий, Вы писали:

Можно было еще вместо стандартного поиска подстроки в строке использовать алгоритм Кнута-Мориса-Прата (прошу прощения если ошибся в написании фамилий, если проще то КМП).

Здравствуйте, zubr, Вы писали:

Z>Здравствуйте, Воронков Василий, Вы писали:

Z>Можно было еще вместо стандартного поиска подстроки в строке использовать алгоритм Кнута-Мориса-Прата (прошу прощения если ошибся в написании фамилий, если проще то КМП).
Лучше БМ, но он сложнее в реализации

Здравствуйте, komaz, Вы писали:

K>Имхо ScanDirectory лучше сделать так:

Чем лучше? Скорее всего это было бы куда медленнее..

Здравствуйте, zubr, Вы писали:

Z>Можно было еще вместо стандартного поиска подстроки в строке использовать алгоритм Кнута-Мориса-Прата (прошу прощения если ошибся в написании фамилий, если проще то КМП).

Если честно, мне кажется что не лучше. В каком году придумали этот алгоритм? С современными мегагерцами String.IndexOf — вполне производительное решение. Например, поиск в файле состоящем из *миллиона* строк длиной в 80 символов занимает на дохлом Celeron 2400 меньше 300 миллисекунд. Конечно, не слишком шустро, но если вспомнить что файл такого размера записанный в 8-битной кодировке занимает под 80 мегабайт..

Здравствуйте, Воронков Василий, Вы писали:

Сомневаюсь что они имели ввиду просто открытие второго потока вначале. Скорее многопоточность касалась операции поиска значения.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Здравствуйте, zubr, Вы писали:

Z>>Можно было еще вместо стандартного поиска подстроки в строке использовать алгоритм Кнута-Мориса-Прата (прошу прощения если ошибся в написании фамилий, если проще то КМП).

ВВ>Если честно, мне кажется что не лучше. В каком году придумали этот алгоритм? С современными мегагерцами String.IndexOf — вполне производительное решение. Например, поиск в файле состоящем из *миллиона* строк длиной в 80 символов занимает на дохлом Celeron 2400 меньше 300 миллисекунд. Конечно, не слишком шустро, но если вспомнить что файл такого размера записанный в 8-битной кодировке занимает под 80 мегабайт..

Какая, говорите, пропускная способность у вашего винчестера?

GZ>Сомневаюсь что они имели ввиду просто открытие второго потока вначале. Скорее многопоточность касалась операции поиска значения.

странно оно как-то, но звучит действительно как будто надо для подкаталогов по потоку создать

Здравствуйте, krasin, Вы писали:

K>Какая, говорите, пропускная способность у вашего винчестера?

Обычный винт, Samsung SP0411N. Заметно медленее скажем популярной нынче Barracuda 7200.8.

Здравствуйте, GlebZ, Вы писали:

GZ>Сомневаюсь что они имели ввиду просто открытие второго потока вначале. Скорее многопоточность касалась операции поиска значения.

Это в принципе можно прикрутить с минимальными изменениями. Так как мы ищем не первый матч а все совпадения то процедуры поиска вообще друг от друга не зависят. Правда, смысла от такого распараллеливания будет ИМХО немного.

Здравствуйте, krasin, Вы писали:

K>Какая, говорите, пропускная способность у вашего винчестера?

А вообще причем здесь винт? Тест я проводил на основе нескольких строк в памяти. И оверхед на IO будет неизбежен какой бы мы алгоритм не избрали. Что как раз и показывает что не в скорость алгоритма поиска мы упираемся.

ВВ>А вообще причем здесь винт? Тест я проводил на основе нескольких строк в памяти. И оверхед на IO будет неизбежен какой бы мы алгоритм не избрали. Что как раз и показывает что не в скорость алгоритма поиска мы упираемся.

Если честно, мне кажется что не лучше. В каком году придумали этот алгоритм? С современными мегагерцами String.IndexOf — вполне производительное решение. Например, поиск в файле состоящем из *миллиона* строк длиной в 80 символов занимает на дохлом Celeron 2400 меньше 300 миллисекунд. Конечно, не слишком шустро, но если вспомнить что файл такого размера записанный в 8-битной кодировке занимает под 80 мегабайт..

эээ... нескольких?!

Здравствуйте, Воронков Василий, Вы писали:

K>>Какая, говорите, пропускная способность у вашего винчестера?

ВВ>А вообще причем здесь винт? Тест я проводил на основе нескольких строк в памяти. И оверхед на IO будет неизбежен какой бы мы алгоритм не избрали. Что как раз и показывает что не в скорость алгоритма поиска мы упираемся.
Если они не находятся в кэше.

Здравствуйте, vitaly_spb, Вы писали:

_>эээ... нескольких?!

Вариант из 5 строк прогоняется 200 тыс. раз.

Здравствуйте, GlebZ, Вы писали:

GZ>Если они не находятся в кэше.

Если имеется в виду программный кэш, то в случае с Find in Files (о чем собственно и идет речь, если я конечно правильно понял) он как бы не особо поможет. Да и кэш винта строго говоря тоже.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Здравствуйте, krasin, Вы писали:

K>>Какая, говорите, пропускная способность у вашего винчестера?

ВВ>Обычный винт, Samsung SP0411N. Заметно медленее скажем популярной нынче Barracuda 7200.8.

Потому что у вас скорость передачи данных 133 Мб/с, а в тесте >80*3 = 240 Мб/с. Хотя это не имеет отношения к замеру скорости сравнения строк, явное несоответствие заявляемых данных действительным не клево.

Здравствуйте, krasin, Вы писали:

K>Потому что у вас скорость передачи данных 133 Мб/с, а в тесте >80*3 = 240 Мб/с. Хотя это не имеет отношения к замеру скорости сравнения строк, явное несоответствие заявляемых данных действительным не клево.

Я не скорость IO мерю. Ее мерять вообще бессмысленно, когда речь идет об алгоритмах поиска в строке. Объяснять почему?

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Здравствуйте, komaz, Вы писали:

K>>Имхо ScanDirectory лучше сделать так:

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

Здравствуйте, komaz, Вы писали:

ВВ>>Чем лучше? Скорее всего это было бы куда медленнее..
K>Согласен, но на мой взгляд это было бы более похоже на ту многозадачность, которую хотели бы увидеть проверяющие.

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

Здравствуйте, trotski, Вы писали:

[skip]

T>Как все это сделать правильней и элегантней? Научите идиота.

А на чём завалился-то? Не работает что-то, или им хотелось что-то иного?

C Уважением, Andir!

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Здравствуйте, GlebZ, Вы писали:

GZ>>Сомневаюсь что они имели ввиду просто открытие второго потока вначале. Скорее многопоточность касалась операции поиска значения.

ВВ>Это в принципе можно прикрутить с минимальными изменениями. Так как мы ищем не первый матч а все совпадения то процедуры поиска вообще друг от друга не зависят. Правда, смысла от такого распараллеливания будет ИМХО немного.

Более того, на нормальной однопроцессорной системе смысл будет в снижении быстродействия. Проц УЖЕ ищет значение. Не нада ему мешать созданием дополнительных нитей, которые, кстати, сожрут часть ресурсов просто фактом своего появления, еще даже не сделав ничего полезного. Проц все-равно не будет искать РЕАЛЬНО два значения паралелльно. Вместо того, что бы сосредоточить его на одной задаче мы заставим его переключаться между одной и той же задачей, но в разных потоках. Классический пример того, что самое сложное в многозадачности — это понимание того, что зачастую она ВРЕДНА и только изредка действительно полезна. Ну и уменее, конечно, отделять первые варианты от вторых. Что возможно даже важнее умения грамотно вторые варианты реализовывать.

Здравствуйте, Smarty, Вы писали:

S>Более того, на нормальной однопроцессорной системе смысл будет в снижении быстродействия. Проц УЖЕ ищет значение. Не нада ему мешать созданием дополнительных нитей, которые, кстати, сожрут часть ресурсов просто фактом своего появления, еще даже не сделав ничего полезного. Проц все-равно не будет искать РЕАЛЬНО два значения паралелльно. Вместо того, что бы сосредоточить его на одной задаче мы заставим его переключаться между одной и той же задачей, но в разных потоках. Классический пример того, что самое сложное в многозадачности — это понимание того, что зачастую она ВРЕДНА и только изредка действительно полезна. Ну и уменее, конечно, отделять первые варианты от вторых. Что возможно даже важнее умения грамотно вторые варианты реализовывать.
Не все так просто. Чтение с дисковых устройств происходит через DMA канал. Использование процессора при этом практически нулевое. В это время вполне можно заниматься чем нибудь полезным. За счет этого, даже на однопроцессорной машине для двух задач будет выйгрыш. Каков выйгрыш получится зависит от данных.

Здравствуйте, GlebZ, Вы писали:

GZ>Не все так просто. Чтение с дисковых устройств происходит через DMA канал. Использование процессора при этом практически нулевое. В это время вполне можно заниматься чем нибудь полезным. За счет этого, даже на однопроцессорной машине для двух задач будет выйгрыш. Каков выйгрыш получится зависит от данных.

Но так пардон — как выяснили выше(Вы же сами, кстати):

Скорее многопоточность касалась операции поиска значения.

Т.е. исходим из того, что данные УЖЕ в памяти и вот в этот момент проверяющие хотели зачем-то видеть стартующую многозадачность поиска. Вот исходя из этого я и писал свой мессаг... Кстати — о ДМА... это, конечно, уже чисто эмпирические рассуждения (т.е. строгое ИМХО), но представляется, что и в этом сценарии(допустим проверяющие на него намекали) с многозадачности можно поиметь "хоть шерсти клок" лишь в случае, если файл(каждый) будет размером метров 5, не меньше. И только если он сразу, целиком заливаться в память будет. При размерах файла 10-100 килограмм многозадачность опять в пролете — слишком мгновенно будут подгоняться новые данные.