Контейнер для коллизий в хеш-таблице

В каноничной хеш-таблице в случае возниконовения коллизий элементы с равным хешем помещаются в связный список. Это приводит к тому, что поиск по контейнеру стоит O(n). Почему для контейнера не использовать другую структуру данных? Например, красно-черное дерево. Или другую хеш-таблицу с другим хешем. Поиск и удаление в таком случае удешевляется. Правда, вставка становится заметно дороже. Цена вставки новых элементов перевешивает цену поиска? Есть ли какие-нибудь библиотеки в любом из современных языков, что позволяют выбирать контейнер для коллизий? Например, можно было бы придумать такой случай: сначала я заполняю хеш-таблицу, а после точно знаю, что мне очень сильно понадобится быстрый поиск - так я возьму и преобразую контейнеры в более подходящие. Или я заранее осознаю стоимость вставки, но поиск все равно гораздо важней.

Ответ

Поиск будет давать O(n) в случае крайне плохого хэша, когда все элементы будут иметь один и тот же хэш. При нормально подобранной хэш-функции получается O(1)
Однако в случае алгоритмов стандарт не написан :), так что да, вполне можно использовать и иные методы разрешения коллизий. Список можно заменять деревом, массивом или даже иной хэш-таблицей с другой хэш-функцией - в конце-концов, идеальное хеширование (см., например, Кормен и др. Алгоритмы. Построение и анализ) именно так и поступает.
Вопрос в заложенных в O() константах. При небольших размерах цепочек поиск (и особенно вставка, когда она играет роль) в них может проводиться быстрее за счет малой константы, чем в более быстрой, но более сложной структуре.
Более того, тут уже начинают играть свою роль и другие факторы, такие как использование кэша процессора и т.п. не совсем алгоритмические мелочи.
Так что для достижения максимального быстродействия, пожалуй, есть только один путь - практически-экспериментальный, и давать он может для каждой связки задача+машина свое решение...

Различие между использованием var и dynamic в foreach

У меня 2 вопроса:
1) Почему в 1-м foreach на переменной name недоступны члены DictionaryEntry(например, name.Value),ведь она принадлежит(или как правильно сказать) типу DictionaryEntry,а во 2-м foreach-всё good?
static void Main() { var emailLookup = new Hashtable();
emailLookup["sbishop@contoso.com"] = "Bishop, Scott"; emailLookup["chess@contoso.com"] = "Hell, Christian"; emailLookup["djump@contoso.com"] = "Jump, Dan";
foreach (var name in emailLookup) { Console.WriteLine(name); }
Console.WriteLine(new string('-', 20));
foreach (DictionaryEntry name in emailLookup) { Console.WriteLine(name); }
Console.WriteLine(new string('-', 20));
foreach (object name in emailLookup.Values) { Console.WriteLine(name); }
// Delay. Console.ReadKey(); }
2) Почему в нижеприведённом примере,в foreach при использовании var - нет доступа к Key и Value,а при использовании dynamic - есть?
class UserCollection { public static IEnumerable Generator() { yield return new { Key = 0, Value = "Zero" }; yield return new { Key = 1, Value = "One" }; yield return new { Key = 2, Value = "Two" }; } }
class Program { static void Main() { foreach (var item in UserCollection.Generator()) { Console.WriteLine("Key = {0}, Value = {1}", item.Key, item.Value); }
// Delay. Console.ReadKey(); } }

Ответ

Почему в 1-м foreach на переменной name недоступны члены DictionaryEntry(например,name.Value)
Потому что в этом случае name это DictionaryEntry упакованный в object. И так как у object нет свойств key, value они и недоступны.
Во втором foreach - происходит явное приведение к DictionaryEntry, поэтому name не упакованный объект, а непосредственно структура, с нужными полями.
Почему в нижеприведённом примере,в foreach при использовании var-нет доступа к Key и Value
Потому что из функции возвращается IEnumerable - это нетипизированная коллекция и item опять является упакованным в object
С dynamic это работает потому, что проверка на существование свойств происходит не во время компиляции, а во время выполнения, так как реально возвращается объект с нужными полями, ошибки не возникает.
Больше про упаковку можно прочитать в MSDN: Упаковка-преобразование и распаковка-преобразование Больше про использования dynamic можно прочитать в MSDN: Использование типа dynamic

Зачем в Python 3.3 ввели list.copy() если можно использовать слайс без указания границ?

Сейчас плотно изучаю нюансы методов встроенных типов, и есть один вопрос, на который не могу найти ответ.
В Python 3.3 ввели метод списка copy(), который делает поверхностную копию. Но то же самое можно было делать, просто взяв срез без границ - list[:]
Зачем было вводить новый метод?
Подозреваю, что какая-то причина есть. Например, сначала я считал таким же ненужным нововведением метод list.clear(), введённый в том же Python 3.3, ведь есть же list = []
А потом я прочитал, что эти две синтаксические конструкции по разному работают в ситуациях, когда на список ссылаются две или более переменных.
Подозреваю, что и для copy() существует такое же очевидное задним числом обоснование, но найти его пока не смог.

Ответ

Чтобы сделать операции del list_[:] и shallow_copy = list_[:] более очевидными (discoverable) и читаемыми для новичков (list_.clear() и shallow_copy = list_.copy() соответственно). See Add list.clear() and list.copy()
В целом, в Питоне есть предпочтение к использованию слов вместо пунктуации, например: and, or вместо &&, || или on_true if cond else on_false вместо cond ? on_true : on_false или re.search(regex) вместо /regex/
Дополнительно, наличие явного метода list_.clear() может уменьшить вероятность возможной ошибки:list_ = [] существенно отличается от del list_[:] (первая конструкция создаёт новый список и привязывает его к имени list_, вторая конструкция удаляет все элементы из существующего объекта (изменяемой последовательности такой как список наиболее вероятно)).
Недостаток, что эти методы дублируют функциональность изменяемых последовательностей/отображений (объекты с __getitem__, __delitem__ методами).

Как сделать выборку по значению из JSON

Имеется таблица с полем типа json. Таблица заполнена значениями вида [123,854,12], [], [12,2142141,24] Как мне выбрать строку, в json которой содержится определенное число? Т.е. если я ищу 12, то я должен получить две строки со значениями, перечисленными выше.

Ответ

Если вы задействуете PostgreSQL вам разумнее воспользоваться не JSON, a типом ARRAY
CREATE TABLE tbl ( id INTEGER, name INTEGER ARRAY ); INSERT INTO tbl VALUES (1, '{123,854,12}'); INSERT INTO tbl VALUES (2, '{}'); INSERT INTO tbl VALUES (3, '{12,2142141,24}');
Тогда для поиска строк, в массиве name которых имеется значение 12 можно воспользоваться следующим запросом
SELECT * FROM tbl WHERE 12 = ANY (name); id | name ----+----------------- 1 | {123,854,12} 3 | {12,2142141,24}

Как узнать установлен ли Skype

Запускаю skype вот таким кодом.
Intent skype_intent = new Intent("android.intent.action.VIEW"); skype_intent.setClassName("com.skype.raider", "com.skype.raider.Main"); skype_intent.setData(Uri.parse("skype: skype_name")); startActivity(skype_intent);
Все нормально. Но если на телефон нету skype, то приложение крашится. Как мне по другому вызвать скайп, чтоб он не крашил приложение или сделать проверку на наличие skype на телефоне. Если есть запустить код, если нет вывести "У вас нету skype"?

Ответ

Думаю в пояснении данный код не нуждается:
private boolean isAppInstalled(String packageName) { PackageManager pm = getPackageManager(); boolean installed = false; try { pm.getPackageInfo(packageName, PackageManager.GET_ACTIVITIES); installed = true; } catch (PackageManager.NameNotFoundException e) { installed = false; } return installed; }

Что происходит со сборкой?

Получилась следующая ситуация...
1) Создаем в приложении домен. 2) Загружаем в него через DoCallBack сборку Assembly.Load(...) 3) Из главного домена достаем сборки ранее созданного и например, показываем их имена. 4) Смотрим какие сборки есть в главном домене, а конкретней - там появилась эта сборка которую мы загрузили в другой домен.
То есть, загружая сборку в другой домен, если обратиться с методу GetAssemblies, загруженные сборки появляются и в основном домене, при этом они не просто туда переносятся, они копируются - их можно использоваться в обоих доменах.
Если зациклить данный процесс и наблюдать за памятью, то видно что она растет, значит сборки загружаются по новой в память каждый раз.
Самый главный вопрос, почему? Как избавиться от переноса сборки в основной домен? Тут даже не в памяти дело, а в том что основной домен держит референс на сборку и не дает её удалить, например. А инфу как-то вытаскивать надо.
class Program { static void Main ( string [ ] args ) { var appDomain = AppDomain.CreateDomain("TestDomain"); appDomain.DoCallBack(LoadModule);
var assembly = appDomain.GetAssemblies().Single( t => t.GetName().Name == "TestModule" );
foreach ( var assembly1 in AppDomain.CurrentDomain.GetAssemblies() ) { Console.WriteLine( assembly1.FullName ); } }
private static void LoadModule() { Assembly.Load( "TestModule" ); } }

Ответ

Существует две возможности передать объект через границу домена приложения:
Через прокси. Для объектов наследующих от System.MarshalByRefObject. При этом все вызовы методов на прокси объекте автоматически перенаправляются в домен приложения, которому принадлежит исходный объект. Через бинарную сериализацию. Для объектов, которые её поддерживают. При этом создаётся копия объекта, которая более не связана с исходным объектом.
При этом класс System.AppDomain наследует от System.MarshalByRefObject, в то время как класс System.Reflection.Assembly нет. То есть вызов appDomain.GetAssemblies() в Вашем коде будет перенаправлен в дополнительный домен приложения, после чего результат его работы (Assembly[]) необходимо будет передать в основной домен приложения: сериализовать в дополнительном домене и десериализовать в основном домене. Данная передача Assembly объектов в основной домен приложения и приводит к загрузке в него сборок.
Чтобы избежать загрузки сборок в основной домен, не передавайте в него объекты, для десериализации которых необходимо загрузить сборку. Как то System.Reflection.Assembly объект, представляющий сборку, System.Type объект, представляющий любой тип из сборки, экземпляр любого типа из сборки.
Например имена сборок можно извлекать в дополнительном домене приложения, а в основной передавать только строки:
using System; using System.Linq; using System.Reflection;
class Program { static void Main ( string [ ] args ) { var appDomain = AppDomain.CreateDomain("TestDomain"); appDomain.DoCallBack(LoadModule);
var worker = (Worker)appDomain.CreateInstanceAndUnwrap(typeof(Worker).Assembly.FullName, typeof(Worker).FullName);
foreach ( var assemblyFullName1 in worker.GetAssembliesFullName() ) { Console.WriteLine( assemblyFullName1 ); } Console.WriteLine(); foreach ( var assembly1 in AppDomain.CurrentDomain.GetAssemblies() ) { Console.WriteLine( assembly1.FullName ); } }
private static void LoadModule() { Assembly.Load( "TestModule" ); } }
class Worker : MarshalByRefObject { public string[] GetAssembliesFullName() { return AppDomain.CurrentDomain.GetAssemblies().Select(a => a.FullName).ToArray(); } }

Какая разница между понятием “селектор” и “фильтр” в jQuery?

Привет.
Не понимаю разницу между понятием "селектор" и "фильтр". В некоторых учебных материалах этапы обучения джейквери называются, например, 1. Выборка 2. Фильтры. Например, пишут, что :first - это фильтр. По-моему, это просто псевдоэлемент, который придумали при написании джейквери.
Не понимаю правил комбинирования селекторов. Какие-то есть правила, как написать сложный селектор? Можно ли использовать несколько псевдоэлементов сразу, например, p.class:first-child:first:visible...

Ответ

Стандарты W3C
Селекторы - это критерии для выборки определенного элемента со страницы, набор селекторов и их комбинирование называется шаблоном. Есть множество селекторов - это селекторы атрибутов, селекторы классов, псевдо-классы, псевдо-элементы и т.д.
W3C говорит
Эти шаблоны, называемые селекторами, могут изменяться в диапазоне от простых имен элементов до сложных текстовых структур. Если определенный элемент удовлетворяет всем критериям, устанавливаемым шаблоном, то соответствующий селектор сопоставляется данному элементу.
Упрощенная терминология
Часто для упрощения, при написании шаблона на выборку, говорят так, что есть селектор, которым называют выборку по элементам (.class например) и есть фильтры, последним, для удобства, называют совокупность псевдо-классов или псевдо-элементов: $(селектор:фильтры).
Селекторы - строчные выражения, с помощью которых задаются условия поиска элементов DOM на странице (.className, #id, ..) Фильтры - это строчные выражения с помощью которых можно уточнить результат других селекторов (:first, :last, ...)
Комбинирование
Комбинирование нескольких фильтров возможно и ваш пример будет работать, попробуем перевести его на русский: выбрать элементы p с классом "class" которые являются первыми в своих родительских элементах, взять первый подобный элемент, после чего проверить что он виден на странице и вернуть его, если это так.
Более адекватный пример: $('#results:odd:has('img')'). В данном случае мы выбираем все нечетные элементы с id="results", которые содержат элементы img, то есть изображения.
Полезная информация
Читаем вот здесь про существующие селекторы, вот здесь про их комбинирование.