Есть ли O (1) структуры данных произвольного доступа, которые не полагаются на непрерывное устройство хранения данных?
Вы можете проверить расширение файла, содержащее mp4, например:
# Add SharePoint Snapin to PowerShell
# Вы можете проверить расширение файла, содержащее mp4, например:
[110].extension -eq $FileExtension
if((Get-PSSnapin | Where { Вы можете проверить расширение файла, содержащее mp4, например:
[110].Name -eq "Microsoft.SharePoint.PowerShell"}) -eq $null) {
Add-PSSnapin Microsoft.SharePoint.PowerShell
}
$web = Get-SPWeb "http://sp:12001/"
$Data = foreach ($list in $web.Lists["MyDoc"]) {
if ($list.BaseType -eq "DocumentLibrary"){
#if ($item -Like "*.mp4"){
foreach ($item in $list.Items) {
$fileExtension= $item.File.Name.Split('.')[1]
if($fileExtension -eq 'mp4'){
$data = @{
"List Name" = $list.Title
"Created By" = $item["Author"]
"Created Date" = $item["Created"]
"Modified By" = $item["Editor"]
"Modified Date" = $item["Modified"]
"Item Name" = $item.File.Name
"URL"=$web.Site.MakeFullUrl("$($web.ServerRelativeUrl.TrimEnd('/'))/$($item.Url)");
}
New-Object PSObject -Property $data | Select "List Name", "Item Name", "Created By", "Created Date", "Modified By", "Modified Date", "URL"
#}
}
}
}
$web.Dispose()
}
11 ответов
Как насчет trie, где длина ключей ограничена некоторым постоянным K (например, 4 байта, таким образом, можно использовать 32-разрядные целые числа в качестве индексов). Затем время поиска будет O (K), т.е. O (1) с памятью, состоящей из нескольких несмежных участков. Кажется разумным мне.
При вспоминании наших классов сложности не забывайте, что каждое большое-O имеет постоянный множитель, т.е. O (n) + C, Этот подход будет, конечно, иметь намного больший C, чем действительный массив.
Править: На самом деле, теперь, когда я думаю об этом, это - O (K*A), где A является размером "алфавита". Каждый узел должен иметь список до дочерние узлы, которые должны будут быть связанным списком, сохраняют реализацию, состоящей из нескольких несмежных участков. Но A является все еще постоянным, таким образом, это все еще O (1).
Кроме хеш-таблицы, у Вас может быть двухуровневый массив массивов:
- Сохраните первые 10 000 элементов в первом подмассиве
- Сохраните следующие 10 000 элементов в следующем подмассиве
- и т.д.
На практике, для небольших наборов данных с помощью непрерывного устройства хранения данных не проблема, и для больших наборов данных O (журнал (n)) так же хорошо как O (1); постоянный множитель скорее более важен.
На самом деле, Для ДЕЙСТВИТЕЛЬНО больших наборов данных, O (root3 (n)) произвольный доступ является лучшим, можно войти в 3-мерную физическую вселенную.
Править: При принятии log10 и O (журнал (n)) алгоритм, являющийся дважды с такой скоростью, как O (1) один в миллионе элементов, потребуется триллион элементов для них для становления даже, и квинтильон для O (1) алгоритм для становления вдвое более быстрым - скорее больше, чем даже самые большие базы данных по земле имеют.
Все текущие и обозримые технологии хранения требуют определенного физического пространства (давайте назовем его v) сохранить каждый элемент данных. В 3-мерной вселенной это означает для n элементов существует минимальное расстояние root3 (n*v*3/4/pi) между по крайней мере некоторыми элементами и место, которое делает поиск, потому что это - радиус сферы объема n*v. И затем, скорость света дает физическую нижнюю границу root3 (n*v*3/4/pi)/c в течение времени доступа к тем элементам - и это - O (root3 (n)), какой необычный алгоритм Вы используете.
Таким образом могло быть желательно иметь структуру данных, которая имеет O (1) произвольный доступ, все же не полагается на непрерывное устройство хранения данных.
Есть что-то такое?
Нет, нет. Эскиз доказательства:
Если у Вас есть предел на Ваш непрерывный размер блока, то, очевидно, необходимо будет использовать косвенность для получения до элементов данных. Фиксированная глубина косвенности с ограниченным размером блока получает Вас только график фиксированного размера (хотя его размер растет экспоненциально с глубиной), поэтому как Ваш набор данных растет, косвенная глубина вырастет (только логарифмически, но не O (1)).
Хеш-таблица?
Править: Массив O(1) поиск, потому что a[i] просто синтаксический сахар для *(a+i). Другими словами, для получения O(1), Вам нужны или прямой указатель или в легко вычисленный указатель на каждый элемент (наряду с хорошим чувством, что память, Вы собираетесь поиск, для Вашей программы). В отсутствие наличия указателя на каждый элемент это вряд ли будет иметь легко вычисленный указатель (и знать, что память зарезервирована для Вас) без непрерывной памяти.
Конечно, вероятно (если ужасный) иметь реализацию Хеш-таблицы, где адрес памяти каждого поиска просто *(a + hash(i)) Не будучи сделанным в массиве, т.е. будучи динамично созданным в указанной ячейке памяти, если Вы имеете такой контроль.. дело в том, что наиболее эффективное внедрение будет основным массивом, но, конечно, вероятно получить удары в другом месте, чтобы сделать реализацию WTF, которая все еще получает Вас постоянно-разовый поиск.
Edit2: Моя точка - то, что массив полагается на непрерывную память, потому что это - синтаксический сахар, но Хеш-таблица выбирает массив, потому что это - лучший метод внедрения, не потому что это требуется. Конечно, я должен читать DailyWTF слишком много, так как я предполагаю перегружать оператор индекса массива C++, чтобы также сделать это без непрерывной памяти тем же способом..
Конечно, о чем Вы говорите вот, не непрерывного устройства хранения данных памяти как такового, но больше способность индексировать содержание структуры данных. Распространено внутренне реализовать динамический массив или список как массив указателей с фактическим содержанием каждого элемента в другом месте в памяти. Существует много причин того, чтобы сделать это - не в последнюю очередь, что это позволяет каждой записи быть различным размером. Как другие указали, большинство реализаций хеш-таблицы также полагается на индексацию также. Я не могу думать о способе реализовать O (1) алгоритм, который не полагается на индексацию, но это подразумевает непрерывную память для индекса, по крайней мере.
Кроме очевидных вложенных структур на конечную глубину, отмеченную другими, я не знаю о структуре данных со свойствами, которые Вы описываете. Я совместно использую мнения других, что с хорошо разработанной логарифмической структурой данных, у Вас может быть память, состоящая из нескольких несмежных участков, с временами с быстрым доступом к любым данным, которые поместятся в оперативную память.
Я знаю об интересной и тесно связанной структуре данных:
- Веревки кедра являются неизменными строками, которые обеспечивают логарифмический а не постоянно-разовый доступ, но они действительно обеспечивают постоянно-разовую операцию конкатенации и эффективную вставку символов. Бумага защищена авторским правом, но существует объяснение Википедии.
Эта структура данных достаточно эффективна, что можно представить все содержание большого файла с помощью нее, и реализация достаточно умна для хранения битов на диске, если Вам не нужны они.
Распределенные карты хеша имеют такое свойство. Ну, на самом деле, не совсем, в основном хеш-функция говорит Вам, какой блок устройства хранения данных заглянуть, там необходимо будет, вероятно, полагаться на традиционные карты хеша. Это не полностью покрывает Ваши требования как список, содержащий области хранения / узлы (в распределенном сценарии), снова, являются обычно картой хеша (по существу делающий это хеш-таблица хеш-таблиц), хотя Вы могли использовать некоторый другой алгоритм, например, если количество областей хранения известно.
Править:
Забыл немного лакомого кусочка, Вы, вероятно, захотите использовать различные хеш-функции для разных уровней, иначе Вы закончите с большим количеством подобных значений хэш-функции в каждой области хранения.
Возможно выделить блок памяти не для целых данных, но только для ссылочного массива к частям данных. Это приносит уменьшение значительного увеличения в продолжительность необходимой непрерывной памяти.
Другая опция, Если элементы могут быть отождествлены с ключами и этими ключами, может быть исключительно отображена на доступных ячейках памяти, возможно не поместить все объекты непрерывно, оставляя пробелы между ними. Это требует управления выделением памяти, таким образом, можно все еще распространить память бесплатно и переместить 2-е priroty объекты к где-то в другом месте, когда необходимо использовать ту ячейку памяти для объекта 1-го приоритета. Они все еще были бы непрерывны в подразмере, все же.
Я могу назвать структуру общих данных, которая отвечает на Ваш вопрос? Нет.
Определенное любопытство: хеш trie оставляет свободное место путем чередования в памяти ключевых массивов trie узлов, которые, оказывается, не сталкиваются. Таким образом, если узел 1 имеет ключи A, B, D, в то время как узел 2 имеет ключи C, X, Y, Z, например, затем можно использовать то же непрерывное устройство хранения данных для обоих узлов сразу. Это обобщено к различным смещениям и произвольному числу узлов; Knuth использовал это в его программе больше-всего-общих-слов в Грамотном программировании.
Таким образом, это дает O (1) доступ к ключам любого данного узла, не резервируя непрерывное устройство хранения данных к нему, хотя с помощью непрерывного устройства хранения данных для всех узлов коллективно.
Некоторый псевдо O (1) ответы -
VList является O (1) доступ (в среднем) и не требует, чтобы все данные были непрерывны, хотя это действительно требует непрерывного устройства хранения данных в маленьких блоках. Другие структуры данных на основе числовых представлений также амортизируются O (1).
Числовое представление применяет тот же 'обман', который вид основания делает, приводя к O (k) структура доступа - если существует другая верхняя граница индекса, такого как он являющийся интервалом на 64 бита, затем двоичное дерево, где каждый уровень соответствуют немного в индексе, занимает постоянное время. Конечно, тот постоянный k больше, чем lnN для любого N, который может использоваться со структурой, таким образом, это вряд ли будет повышение производительности (вид основания может получить повышения производительности, если k только немного больше, чем lnN и реализация вида основания выполняют лучшее использование платформа).
При использовании того же представления двоичного дерева, которое распространено в реализациях "кучи", Вы заканчиваете назад в массиве.