Поиск дубликатов файлов

Задание:

Написать программу, которая осуществляет поиск дубликатов файлов.

На вход подаётся путь, по которому должен осуществляться поиск. На выходе - текстовый файл, в котором будут указаны все дубликаты, по 1 пути на строку.

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

Решение на PHP:

<?php

class EmptySetException extends Exception {}
class FilePermissionException extends Exception {}
class DirExistanceException extends Exception {}
class NoDuplicatesException extends Exception {}

/*
 * @author Oleksii Danylevskyi 
 *
 * Directory scanner class
 */
class Dir {
	// Result file path
	private $resultFile;
	// Scanning directory path
	private $dirs;
	
	/*
	 * Dir entity constructor 
	 * @param - string
	 *   $path - scanning directory path
	 * @param - string
	 *   $resultFile - result file path
	 *
	 * @throws - DirExistanceException
	 */
	public function __construct($path = null, $resultFile = null) {
		if (!$path) {
			$path = getcwd();
		} else if (!file_exists($path)) {
			throw new DirExistanceException('Directory does not exist. Please, check the path you want scan.', 0);
		}
		$this->dirs  = array();
		array_push($this->dirs, $path);
		
		if (!$resultFile) {
			$resultFile = getcwd().DIRECTORY_SEPARATOR.'youcontrol-duplicates.txt';
		}
		if (file_exists($resultFile)) {
			unlink($resultFile);
		}
		$this->resultFile = $resultFile;
	}
	
	/*
	 * Check dir and it's subdirs for duplicates
	 *
	 * @throws - EmptySetException
	 *   if dir and subdirs have no duplicates 
	 */
	public function checkDuplicateFiles() {
		$duplicates = array();
		
		while(!empty($this->dirs)) {
			$currentDir = array_pop($this->dirs);
			foreach(scandir($currentDir) as $name) {
				if (strcmp($name, '.') != 0 && strcmp($name, '..') != 0) {
					$currentName = $currentDir.DIRECTORY_SEPARATOR.$name;
					if (is_dir($currentName)) {
						array_push($this->dirs, $currentName);
					} else {
						$duplicates[$name][] = $currentDir;
					}
				}
			}
		}
		
		if (empty($duplicates)) {
			throw new EmptySetException('You have no duplicate files.', 0);
		} else {
			$this->duplicatesToResultFile($duplicates);
		}
	}
	
	/*
	 * Put all duplicates in result file
	 *
	 * @throws - FilePermisionException, NoDuplicatesException
	 *   FilePermisionException - if you have no permissins to write to result file
	 *   NoDuplicatesException - if there is no duplicates in the folder
	 */
	protected function duplicatesToResultFile($duplicates = []) {
		$hasNoDublicates = true;
		foreach($duplicates as $name => $pathArr) {
			if (count($duplicates[$name]) == 1) {
				unset($duplicates[$name]);
			} else {
				$hasNoDublicates = false;
				foreach($pathArr as $path) {
					$result = @file_put_contents($this->resultFile, $path.DIRECTORY_SEPARATOR.$name.PHP_EOL, FILE_APPEND);
					if ($result === FALSE) {
						throw new FilePermissionException('You don\'t have permission to create '.$this->resultFile.' file. Please, check your permission.');
					}
				}
				file_put_contents($this->resultFile, PHP_EOL, FILE_APPEND);
			}
		}
		if ($hasNoDublicates) {
			throw new NoDuplicatesException('There is no duplicates in the folder.', 0);
		}
	}
	
	/*
	 * Return result file path
	 *
	 * @return - string
	 *   file to result path
	 */
	public function getResultFile() {
		return $this->resultFile;
	}
}

Пример использование


try {
// Путь который будет проверяться
$pathToCheckDuplicates = getcwd().DIRECTORY_SEPARATOR.'test';
$dir = new Dir($pathToCheckDuplicates);
$dir->duplicateFiles();
die('Done! Check the answer file here: '.$dir->getResultFile().' .');
} catch (Exception $e) {
die($e->getMessage());
}

Производительность

Предствим, что дана проверяемая папка имеет в себе N подпапок(влючая подпапки подпапок) и M файлов (включая файли подпапок), тогда общая сложность алгоритма будет O(N*M), а используемое пространство будет равно O(N+M). 

LikeMe: