haskell - Why does "nub" have O(n^2) complexity when it could be O(n)? -

-

the nub function data.list has o(n2) complexity. it's clear implementing o(n) algorithm doable , not hard. why doesn't haskell it?

 nub :: eq => [a] -> [a] base data.list o(n^2). nub function removes duplicate elements list. in particular, keeps first occurrence of each element. (the name nub means `essence'.) special case of nubby, allows programmer supply own equality test.

to provide answer has been made rather painfully explicit in comments: premise wrong, nub :: eq => [a] -> [a] can not have o(n) implementation.

you thinking of implementation can assume ordering, ordnub :: ord => [a] -> [a], linear log. or perhaps assuming hashable, bucket-sortable sort of thing. unlike eq, when have ordering information don't need potentially compare every pair of elements.

this topic discussed in 2008: http://haskell.1045720.n5.nabble.com/ghc-2717-add-nubwith-nubord-td3159919.html

this topic discussed again, different actors in community, in 2013: https://www.haskell.org/pipermail/haskell-cafe/2013-october/110984.html


Comments

Post a Comment

Popular posts from this blog

google api - Incomplete response from Gmail API threads.list -

-
i plot number of emails in inbox on time using gmail api , i'm seeing lot of drop-outs, whatever reason i'm getting incomplete count of messages @ single time points. my plots here: https://plot.ly/~tdsmith/2 -- "drop-outs" i'm complaining trace shoots downwards , recovers previous level @ next timepoint. the code i'm using count emails here: https://github.com/tdsmith/gmail-plotly/blob/master/gmail-plotly.py#l47-l64 what can diagnose these faults?
Read more

Installing Android SQLite Asset Helper -

-
i need use ready made database. search solution on internet did not work until decided use mentioned library found here . however, found hard use library in installation procedures shallow beginners. i appreciate step step procedure on how use android studio. in struggle tried copying sources main/libs , adding line gradle did not work. use api 19 if helps. update here build.gradle // top-level build file can add configuration options common sub-projects/modules. buildscript { repositories { mavencentral() } dependencies { classpath 'com.android.tools.build:gradle:0.11.+' compile 'com.readystatesoftware.sqliteasset:sqliteassethelper:+' // note: not place application dependencies here; belong // in individual module build.gradle files } } allprojects { repositories { mavencentral() } } trying compile project error error:(9, 0) no signature of method: org.gradle.api.internal.artifacts
Read more

Qt Creator - Searching files with Locator including folder -

-
one quick question qtcreator : know possible use locator open files using "ctrl-k" shortcut. however, possible search files including locations? for example, let's want locate file named "main.cpp" in folder named "myfolder" , have lots of other main.cpp files. what should type locator in order open ? just type myfolder/main.cpp in locator
Read more