LINUX.ORG.RU
Форум — Development  

F# проверка списка на оригинальность и т.п. без хэшей

 


0

1

Добрый день. Я опять возвращаюсь к вопросу, которой уже поднимал около 3х лет назад. Оптимизация поиска _наличия_ общего элемента 2х списков. Это опять оказалось слабым местом в производительности моей программы. 

let original eq l =
    l 
    |> List.fold 
        (fun acc el ->
            if (acc |> List.exists (fun elLater -> eq el elLater))
            then acc else el :: acc)
        []
    |> List.rev

Да, тогда мне насоветовали использовать хэш таблицы и я сильно удивился, открыв код и увидев реализацию в лоб. Я переписал код: 

let original (eq : 'a -> 'a -> bool when 'a : equality) l =
    let hs = new HashSet<'a>(l, Comparer<'a>(eq))
    hs.ToList().AsEnumerable() |> Seq.toList

Производительность разумеется выросла, но программа стала работать неправильно. Учитывая, что я поменял только код этой функции, я написал на неё несколько тестов и они все отработали верно, но программа целиком работала не правильно. Причина этого кроется в реализации Comparer: 

type Comparer<'a>(f) =
    interface System.Collections.Generic.IEqualityComparer<'a> with
        member x.Equals(a, b) =
            f a b
        member x.GetHashCode(a) = hash(a.ToString())
метод .ToString() у многих объектов просто не переопределён и возвращает имя класса. То есть такая реализация путь к множеству ошибок логики. Она, как мне кажется, куда опаснее ошибок типов, так как программа не падает, а просто работает неправильно. Я понимаю, что можно сделать специальный интерфейс и требовать его реализации у всех типов объектов, вызываемых в качестве аргументов. Или заставлять их явно реализовывать IEqualityComparer. Но так теряется выразительность вызова функции List.original и подобных. По сути приходится или частично разделять логику сравнения или полностью переносить её в реализацию типа(и отказаться от сравнения составных данных, к примеру 'a * 'a). Теперь вопрос, как получить производительность аналогичную хэш талбицам, не используя хэш функцию. Или это просто невозможно? В языках, дающих явный доступ к ссылке на объект можно воспользоваться таким сравнением, считая объекты не изменяемыми во время вызова функции. В языках, имеющих функцию сравнения объектов по расположению в памяти, такое тоже можно реализовать довольно просто как мне кажется, но логика немного изменится.

В общем пока что остановился на таком варианте - 

type Comparer<'a>(f, fhash) =
    interface System.Collections.Generic.IEqualityComparer<'a> with
        member x.Equals(a, b) =
            f a b
        member x.GetHashCode(a) = fhash a
         
let originalFast eq hashCode l =
    let hs = new HashSet<'a>(l, Comparer<'a>(eq, hashCode))
    hs.ToList().AsEnumerable() |> Seq.toList      

let original eq l =
    Log.logw "Using not optimized version of List.original"
    l 
    |> List.fold 
        (fun acc el ->
            if (acc |> List.exists (fun elLater -> eq el elLater))
            then acc else el :: acc)
        []
    |> List.rev

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

Ключом будем хеш, вычисленный по объекту через функцию GetHashCode.

dave ★★★★★
()
Ответ на: комментарий от dave

К примеру, ты вызываешь функцию List.original с логикой типа: два объекта равны, если какая-нибудь математическая функция от них равна. В таком случае G(x1) = G(x2), x1 <> x2. Но если хэши этих объектов не равны, то и в словарь они добавятся оба, хотя твою основное условие выполняется. А только оно и интересует когда ты производишь такую запись - 

List.original args1 args2 (fun a b -> g(a) = g(b))
понимаешь какие ошибки влечет использование этой функции при условии не знания её внутреннего устройства?

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

Подожди, ты хочешь написать универсальный IEqualityComparer, не зная самого типа? Если да, то это невозможно.

Только тип может знать, как определить свое отношение эквивалентности. В F# есть equality. Это что-то типа ограничения на класс типов Eq как в haskell, но с умением вычислять хеш-функцию. Каждый тип должен только сам определять свой equality. Ты об этом?

dave ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development