man Рекурсия

(=

Это основное тестовое задание для младшего разработчика компании eSignal =)

Написать нужно либо в MFC, либо в Qt ( но так-как HR-менеджер указывает на портируемость, то писать приходится на Qt =) ).

=)

Вспомнилось просто =)

Можно использовать всё что угодно из Qt?

у меня пока ничего хорошего не получилось.

не важно хорошо или не хорошо, расскажите каким путем вы пошли

Если память не изменяет, то нужно было написать, чтобы программа не подавала признаков зависания при выборе директории и отображении её содержимого (поддиректорий и файлов), также необходимо было выводить статистику по расширениям файлов (всем файлам и в частности по файлам в текущей директории без учёта вложенных директорий). И всё это должно быть реализовано минимумом кода с максимумом «платформонезависимости».

Как-то так. Прямого ограничения на использование возможностей Qt не было.

Смысла нет, проход по папкам упирается не в процессор а в драйвер ФС.

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

пул потоков видимо

А без потока? А то повадились, чуть что, сразу поток.

Действительно, какой смысл? Упирается в IO. Я бы сделал обход и получение файлов однопоточным, а саму обработку, только если она того стоит, можно сделать многопоточной. Например, через акторы, посылая им задания асинхронно. Такое поведение при желании можно имитировать доступными средствами на более простых языках.

Если это для продакшана, а не какое-нибудь учебное задание, то используйте лучше fts_open и не парьтесь.

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

>глубокой (тысячи вложенных каталогов),

ИМХО тысячные уровни вложенности загнут любого. А кто-нибудь видел такую ситуацию. Не, я понимаю есть тысячи объектов в директории, но чтобы тысячи уровней вложенности.

> ИМХО тысячные уровни вложенности загнут любого. А кто-нибудь видел такую ситуацию. Не, я понимаю есть тысячи объектов в директории, но чтобы тысячи уровней вложенности.

Не загнут, если через продолжения писать. Заменить обычную рекурсию на хвостовую. В F# для этого достаточно просто весь код обернуть в монаду Async и, вуаля, будет готово. Но задача, да, выдуманная :)

а gcc ее кстати же поддерживает? хвостовую то.

На Qt такая задачка решается даже без фантазии.

Этого мало. По хорошему нужен еще и gc. Но это все фантазии... У ТС, скорее всего, голый си.

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

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

Нет, конечно. Только монада Async - это самое простое в использовании из того, что мне известно. Там пишется как бы «обычный» код и оборачивается в тег «async { ... }». Затем компилятором такой код автоматически разворачивается в хвостовую рекурсию. Минимум ручной работы :)

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

>по-моему обход дерева каталогов так просто не развернешь.

Я тоже так считаю. Как минимум одну «переменную»/«уровень вложенности» надо иметь. Другое дело, если итеративный процесс будет более экономично расходовать память. Это возможно, но принципиально проблему сверхвысокого уровня вложенности решить не удастся.

нужно каждую папку сканировать отдельным потоком или просто сканирование сделать в потоке отличном от потока в котором крутится GUI messages?

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

>нужно каждую папку сканировать отдельным потоком

А если этих папок ОЧЕНЬ много, то понадобится ОЧЕНЬ много потоков.

>или просто сканирование сделать в потоке отличном от потока в котором крутится GUI messages?

А вот это уже здравая мысль. Я думаю таким решением можно и ограничиться.

Разворачивается. Async не накладывает ограничений. Просто нужно обернуть вычисление в монаду. Тогда все while/for/try преобразуются в функциональную форму с гарантированным TCO. Это же касается рекурсивных вызовов, которые теперь превращаются в применение монадического bind - для него TCO тоже гарантировано. Тем более, что while строится через bind, а for - через while и try.

Это в ответ на ложное на мой взгляд утверждение, что «тысячные уровни вложенности загнут любого». Привел пример, где это не так.

> На Qt такая задачка решается даже без фантазии.

ага, щаззз, на Qt такая задачка решается далеко не оптимальным образом

QDirIterator напрямую не дает информацию, на каталог он указывает или на файл, в результате, так как ТС нужен многопоточный обход, ему потребуется дополнительный вызов stat (например через QFileInfo) на каждый пункт каталога, а это может очень-очень сильно сказаться на скорости

> А если этих папок ОЧЕНЬ много, то понадобится ОЧЕНЬ много потоков

ОЧЕНЬ много потоков для современных систем не экзотика.

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

Гм. Хотя рекурсивные вызовы для прохода по каждой ноде из корневой директории тоже можно написать..

8 мб на стек для потока по умолчанию в современной системе линукс

> QDirIterator напрямую не дает информацию, на каталог он указывает или на файл, в результате, так как ТС нужен многопоточный обход, ему потребуется дополнительный вызов stat (например через QFileInfo) на каждый пункт каталога, а это может очень-очень сильно сказаться на скорости

Есть QDir::entryInfoList()

>файловая система будет оооочень глубокой (тысячи вложенных каталогов)

В природе существует ограничение на максимальную длину пути, если ты не знал. Называется PATH_MAX и срезает «тысячи вложенных каталогов» буквально до пары тысяч при условии, что название каждогокаталога состоит из одного символа.

> Есть QDir::entryInfoList()

не, это просто издевательство какое-то

что, по-твоему, возвращает QDir::entryInfoList()?

Я к тому, что можно вообще без QDirIterator обойтись :)

QDir использует его на внутреннем уровне. Ну и как я написал уже, вызов QFileInfo - это неминуемые тормоза.

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

В общем, самый быстрый способ чтения каталога - это readdir.

>Это в ответ на ложное на мой взгляд утверждение, что «тысячные уровни вложенности загнут любого»

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

Может популярно объяснишь, за счет чего можно достичь константного потребления памяти при обходе неупорядоченного дерева директорий произвольного размера?

> QDir использует его на внутреннем уровне.

Вот лажа, сам ни за что б не подумал. Qt провоцирует лень заглядывания в собственные сорцы..

В общем, самый быстрый способ чтения каталога - это readdir.

Ну так POSIX вообще лучший :)

толстяк.

просто рекурсивный обход есть, но хотелось бы использовать скажем 3-4 потока, но вот как сделать сихронизация между ними не пойму :(

>просто рекурсивный обход есть, но хотелось бы использовать скажем 3-4 потока, но вот как сделать сихронизация между ними не пойму :(

А нельзя ли сделать что-то вроде Jobs и пару рабочих тредов. Каждый Job сканирует дерево до определенной глубины и, если не если не дошел до конца, то добавляет новые задания в очередь. Правда тут надо продумать детали. Очень легко вывалится в огромное количество заданий в очереди. Можно в задании указывать: сканировать элементы в данной директории «от сих до сих» и соответственно каждая директория может породить не более X заданий, вне зависимости от числа элементов в ней. Как-то так.

Ну и вообще тут говорили, что производительность упрется не в процессор а в дисковую подсистему.

а gcc ее кстати же поддерживает? хвостовую то.

Хвостовую - да, упрощает.

(=

Я же не спрашивал как это сделать =)

fts_open - прекрасно справляется. Как-то приходилось писать AV-сканнер (на базе готового AV Engine), который должен быть устойчив к любому содержимому файлопомойки, так что не по наслышке знаю.

Для самоделки рекурсивной достаточно 1-2 тысяч вложенных каталогов, что-бы исчерпать лимит дескрипторов, если на каждом уровне держать открытый хендл (DIR*) директории, и вполне можно нарваться на срыв стека, если на каждом из уровней - перечитывать все содержимое каталога, так что тут нужно что-то очень гармоничное-продуманное, иначе — no way, fts_open наше все.

подробнее можешь?!

(=

Я просто попытался угадать, может это задание какое-то =)

Не-не-не вообще не троллю =)

Разве что оффтопики генерирую =)

>Может популярно объяснишь, за счет чего можно достичь константного потребления памяти при обходе неупорядоченного дерева директорий произвольного размера?

очевидно, за счет изменения представоения дерева. например, в виде массива(списка)

Перевод на С++ и останов всего этого дела оставляю тебе

package org.absurd.mtfswalker;

import java.io.File;
import java.util.LinkedList;

public class Startup {
	static class Queue {
		private LinkedList queue = new LinkedList();
		
		synchronized void put(File file) {
			queue.addLast(file);
			notifyAll();
		}
		
		synchronized File get() throws InterruptedException {
			while (queue.isEmpty()) {
				wait();
			}
			return (File) queue.removeFirst();
		}
	}
	
	static final Queue QUEUE = new Queue();
	
	static class Worker implements Runnable {
		public void run() {
			try {
				while (true) {
					File f = QUEUE.get();
					if (f.isDirectory()) {
						File[] fileList = f.listFiles();
						for (int i = 0; i < fileList.length; i++) {
							if (fileList[i].isDirectory()) {
								QUEUE.put(fileList[i]);
							} else {
								System.out.println("Worker : " + Thread.currentThread().getName() 
										+ " visiting file " + fileList[i].getName());
							}
						}
					}
				}
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
	}
	
	static final int WORKER_COUNT = 4;
	
	public static void main(String[] arg) {
		for (int i = 0; i != WORKER_COUNT; ++i) {
			new Thread(new Worker(), "WORKER_" + i).start();
		}
		QUEUE.put(new File("."));
	}
}

>На Qt такая задачка решается даже без фантазии.

Вот за это и не люблю Qt. Был графический тулкит, а в него понатаскали все, что только возможно.

Напрямую противоречит Unix way: библиотека выполняет одну функцию, но делает это хорошо.