Медленный поиск файлов для больших каталогов

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

источник

2013-11-28 Shashank Shekhar

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

источник

2013-11-28 07:25:51

Amir благодарит за тонну быстрой rply но проблема беспокоит меня, делает JVM пытается сопоставить путь к файлу с объект для каждого и e очень файлы в месте перед его открытием? –

@ShashankShekhar Нет, операционная система выполняет поиск. Это зависит от операционной системы (например, Windows, Linux, Mac OS X) и файловой системы (например, NTFS, ext4). –

@ShashankShekhar, делегаты JVM для ОС. –

Я сделал некоторые измерения с использованием Java 1.6 на Linux 2.6.32 (избегали шума JIT-компилятора) при открытии файла и списке каталогов. Открытие случайного файла должно быть O (LogN) в this, но нет никакого измеримого замедлиться ДО 1 миллиона файлов:

Opened random file in /tmp/fubar.100 in 0 ms 
Last modified at 1385629306000 
Opened random file in /tmp/fubar.1000 in 0 ms 
Last modified at 1385631078000 
Opened random file in /tmp/fubar.10000 in 0 ms 
Last modified at 1385631054000 
Opened random file in /tmp/fubar.100000 in 0 ms 
Last modified at 1385630478000 
Opened random file in /tmp/fubar.1000000 in 0 ms 
Last modified at 1385632681000

Оказывается производительность File.listFiles() является O (п):

Listed 104 files in /tmp/fubar.100 in 2 ms 
Listed 1001 files in /tmp/fubar.1000 in 9 ms (5x) 
Listed 10001 files in /tmp/fubar.10000 in 19 ms (2x) 
Listed 100006 files in /tmp/fubar.100000 in 186 ms (10x) 
Listed 1000002 files in /tmp/fubar.1000000 in 1909 ms (10x)

Трассирование показывает getdents() вызывается несколько раз O (п) раз:

$ grep getdents err.100|wc 
    28 5006 72926 
$ grep getdents err.1000|wc 
    33 44514 669558 
$ grep getdents err.10000|wc 
    147 441327 6765305 
$ grep getdents err.100000|wc 
    1213 4409107 68693705 
$ grep getdents err.1000000|wc 
    11987 44085454 701243406

источник

2013-11-28 10:48:08 gabor

ya это совершенно очевидно, так как Робин сказал, что он зависит от оборудования подчеркивания, os и файловой системы. Большое спасибо за ваши усилия @gabor, теперь я знаю точную сложность листинга файлов. Но я хотел знать сложность проверки существования файла. –

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

Несмотря на то, что он зависит от базовой аппаратной и файловой системы, современные файловые имена хэш-файлов файловой системы (перечисленные выше), поэтому поиск эффективен O (log N). На обратной стороне алфавитный список требует сортировки O (N * log N). – gabor

Медленный поиск файлов для больших каталогов

ответ

Смежные вопросы