I'm working on the Boyer-Moore-Horspool algorithm but Aleksei's Naïvi algorithm solution still being faster as they don't need to use module functions like Enum.at nor Map.has_index?
I'm refactoring my Boyer-Moore code to avoid any module function. [image: image.png] El vie, 15 jul 2022 a las 16:50, Zach Daniel (<[email protected]>) escribió: > Ah, sorry I misunderstood. The names i proposed are not good :) > > > On Fri, Jul 15 2022 at 11:07 AM, Julian Somoza <[email protected]> > wrote: > >> Hi Zach, absolutely no. >> >> List.includes_list?([1, 2, 3], [1, 1, 1]) >> false >> >> I like the idea behind any_contained? and none_contained? >> >> I think all_contained? is not clear about the strict order of the >> elements... >> >> Probably think on the function name is hardest than the logic behind... :) >> >> >> >> El vie, 15 jul 2022 a las 11:21, Zach Daniel (<[email protected]>) >> escribió: >> >>> An interesting question that should be defined that highlights the main >>> difference between MapSet and List: what is the result of >>> `List.includes_sublist?([1, 2, 3], [1, 1, 1])`? If the answer is `true` >>> then I think the function should still be called `List.subset` because that >>> is what its really determining (i.e the implication is that this operation >>> treats the lists as sets). Alternatively, `List.all_contained?(subject, >>> search)` may be clearer, and lends itself to further additions like >>> `List.any_contained?` and `List.none_contained?`. >>> >>> >>> On Fri, Jul 15, 2022 at 10:16 AM, José Valim <[email protected]> >>> wrote: >>> >>>> Thanks for the proposal. >>>> >>>> The issue with contains? is that it is slightly ambiguous in that it is >>>> unclear if List.contains?(list, [1, 2]) is meant to be positive for [[1, >>>> 2]] or [1, 2]. In Strings there is no such ambiguity. So I would personally >>>> avoid contains? in favor of something clearer. Therefore I would love to >>>> see if other languages have this function and what they call it. :) >>>> >>>> Regarding the implementation, I also think one of the several string >>>> lookup techniques could be used here. The recursive approach is better but >>>> it has O(m*n) worst case complexity. The "bad character rule" from >>>> Boyer–Moore >>>> <https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm> >>>> shouldn't add too much complexity and can provide a meaningful improvement. >>>> >>>> On Fri, Jul 15, 2022 at 3:32 PM Julian Somoza <[email protected]> >>>> wrote: >>>> >>>>> Thanks for your replies, >>>>> >>>>> yes, it could be an String.contains? analog: >>>>> >>>>> [1,2,"3",4] |> Enum.join |> String.contains?("34") >>>>> [1,:a,"3",4] |> Enum.join |> String.contains?("a3") >>>>> >>>>> About the recursive version, it seems to have best performance: >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> El vie, 15 jul 2022 a las 9:38, Aleksei Matiushkin (< >>>>> [email protected]>) escribió: >>>>> >>>>>> I have not benchmarked it, but I believe the recursive approach would >>>>>> be better >>>>>> >>>>>> ``` >>>>>> defmodule MyList do >>>>>> def contains?(list, sublist, strict? \\ false) >>>>>> >>>>>> def contains?(_, [], _), do: true >>>>>> def contains?([], _, _), do: false >>>>>> def contains?([h | t], [hh | _] = sub, strict?) when h != hh, do: >>>>>> not strict? and contains?(t, sub, strict?) >>>>>> def contains?([h | t], [h | tt], strict?), do: contains?(t, tt, >>>>>> true) or contains?(t, [h | tt], strict?) >>>>>> end >>>>>> ``` >>>>>> >>>>>> On Fri, Jul 15, 2022 at 2:07 PM 'eksperimental' via elixir-lang-core >>>>>> <[email protected]> wrote: >>>>>> >>>>>>> Hi Julian. >>>>>>> It think it is a good addition. >>>>>>> It is also analog to String.contains?/2 >>>>>>> >>>>>>> On Fri, 15 Jul 2022 04:58:59 -0700 (PDT) >>>>>>> Julian Somoza < >>>>>>> https://urldefense.proofpoint.com/v2/url?u=http-3A__julian.somoza-40gmail.com&d=DwICaQ&c=euGZstcaTDllvimEN8b7jXrwqOf-v5A_CdpgnVfiiMM&r=rmhwzhuTk1LyLPLZIrqkat6wS6r2qE3XZKnTTHGaxH8&m=rZfYwgMRyMdd1mpKac91VLHbd0qUJlcEVeNzbceWXvE&s=T8KKoaIf0UYlrJ_VQC1Qv_48Tje2jygIaQysVTXu2c0&e=> >>>>>>> wrote: >>>>>>> >>>>>>> > Hi everyone, I was working on a suggestion to add a new function on >>>>>>> > the List module in order to find out if a given sublist is inside >>>>>>> > another list. >>>>>>> > >>>>>>> > We currently have *List.starts_with?/2* but this only match the >>>>>>> > beginning: >>>>>>> > >>>>>>> > iex(1)> List.starts_with?([1, 2, 3], [1, 2]) >>>>>>> > true >>>>>>> > >>>>>>> > Besides, we have *MapSet.subset*, but it ignores the elements >>>>>>> order: >>>>>>> > >>>>>>> > iex(1)> MapSet.subset?(MapSet.new([1 >>>>>>> <http://mapset.subset/?(MapSet.new([1>, 2]), MapSet.new >>>>>>> <http://mapset.new/>([1, 2, 3])) >>>>>>> > true >>>>>>> > >>>>>>> > iex(1)> MapSet.subset?(MapSet.new([2 >>>>>>> <http://mapset.subset/?(MapSet.new([2>, 1]), MapSet.new >>>>>>> <http://mapset.new/>([1, 2, 3])) >>>>>>> > true >>>>>>> > >>>>>>> > I suggest a new function that works like *List.starts_with?/2* but >>>>>>> > matches the entire list, either at the beginning, middle, or end of >>>>>>> > the list. >>>>>>> > >>>>>>> > iex(1)> List.includes_sublist?([1,2,3,4,5], [2,3]) >>>>>>> > true >>>>>>> > >>>>>>> > iex(1)> List.includes_sublist?([1,2,3,4,5], [1,2]) >>>>>>> > true >>>>>>> > >>>>>>> > iex(1)> List.includes_sublist?([1,2,3,4,5], [3,4,5]) >>>>>>> > true >>>>>>> > >>>>>>> > iex(1)> List2.includes_sublist?([1,2,3,4,5], [1,5]) >>>>>>> > false >>>>>>> > >>>>>>> > I'm sharing with you also the function code: >>>>>>> > >>>>>>> > >>>>>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_elixir-2Dlang_elixir_pull_11987_commits_2b7eba5f6419f906f565e7d4bfe3d687f3b8b052&d=DwICaQ&c=euGZstcaTDllvimEN8b7jXrwqOf-v5A_CdpgnVfiiMM&r=rmhwzhuTk1LyLPLZIrqkat6wS6r2qE3XZKnTTHGaxH8&m=rZfYwgMRyMdd1mpKac91VLHbd0qUJlcEVeNzbceWXvE&s=rqpOP9kyNDkOSBV-I2zlHssI6EVLQQ-iBW1F0k3nqFg&e= >>>>>>> > >>>>>>> > I aim to complement the List.starts_with?/2. This function could be >>>>>>> > the same or even more useful because it finds the ordered sublist >>>>>>> > also in the middle or in the end. >>>>>>> > >>>>>>> > Looking forward for your comments, >>>>>>> > BR, >>>>>>> > Julian Somoza. >>>>>>> > >>>>>>> > >>>>>>> >>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "elixir-lang-core" group. >>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>> send an email to [email protected]. >>>>>>> To view this discussion on the web visit >>>>>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__groups.google.com_d_msgid_elixir-2Dlang-2Dcore_62d1588e.1c69fb81.3332c.1d2dSMTPIN-5FADDED-5FMISSING-2540gmr-2Dmx.google.com&d=DwICaQ&c=euGZstcaTDllvimEN8b7jXrwqOf-v5A_CdpgnVfiiMM&r=rmhwzhuTk1LyLPLZIrqkat6wS6r2qE3XZKnTTHGaxH8&m=rZfYwgMRyMdd1mpKac91VLHbd0qUJlcEVeNzbceWXvE&s=Ckh5t8xdml-Vx3UgfKMNxh3CoSb8IBfBORyYgVxcXsg&e= >>>>>>> . >>>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> *Aleksei Matiushkin*, Software Engineer - R&D >>>>>> >>>>>> Office (+34) 935 679 834 >>>>>> >>>>>> >>>>>> >>>>>> 8 Devonshire Square, London, EC2M 4PL, United Kingdom >>>>>> Torre Mapfre, Planta 22, Marina, 16-18, 08005 Barcelona, Spain >>>>>> *kantox.com <http://kantox.com/>* >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> <http://www.linkedin.com/company/1871617> >>>>>> <http://www.linkedin.com/company/1871617>[image: LinkedIn] >>>>>> <https://www.linkedin.com/company/1871617> >>>>>> <https://twitter.com/kantox>[image: Twitter] >>>>>> <https://twitter.com/kantox> >>>>>> <http://www.youtube.com/user/kantoxfx>[image: YouTube] >>>>>> <https://www.youtube.com/user/kantoxfx> >>>>>> >>>>>> Kantox Limited is a UK private company with registered company number >>>>>> 07657495 and registered address at 8 Devonshire Square, London EC2M 4PL, >>>>>> United Kingdom. We are authorised with the UK Financial Conduct Authority >>>>>> (FCA) under the Payment Service Regulation 2017 as a Payments Institution >>>>>> (FRN 580343) for the provision of payment services and with HMRC as a >>>>>> Money >>>>>> Service Business Registration No.12641987. >>>>>> Kantox European Union, S.L. is a Spanish private company with tax ID >>>>>> number B67369371 and registered address at Torre Mapfre, Planta 22, >>>>>> Marina, >>>>>> 16-18, 08005 Barcelona, Spain. Kantox is authorized by the Bank of >>>>>> Spain, with registration number 6890, which is the supervisor of the >>>>>> Spanish banking system along with the European Central Bank. >>>>>> Additionally, >>>>>> we are supervised by SEPBLAC, the Supervisory Authority for the >>>>>> prevention >>>>>> of money laundering and terrorist financing in Spain. >>>>>> KANTOX is the Controller for the processing of data in accordance >>>>>> with the GDPR and LOPDGDD for the purpose of maintaining a commercial >>>>>> relationship. You may exercise your rights of access and rectification, >>>>>> portability, restriction and opposition by writing to KANTOX to the >>>>>> email: >>>>>> [email protected]. You have your right to make a complaint at >>>>>> www.aepd.es. >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "elixir-lang-core" group. >>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>> send an email to [email protected]. >>>>>> To view this discussion on the web visit >>>>>> https://groups.google.com/d/msgid/elixir-lang-core/CAGF5_6efo17fReu7sLXYxAO_%3DBdSiPFRSuf_Y1MiKNt1owsoYw%40mail.gmail.com >>>>>> <https://groups.google.com/d/msgid/elixir-lang-core/CAGF5_6efo17fReu7sLXYxAO_%3DBdSiPFRSuf_Y1MiKNt1owsoYw%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>>>> . >>>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "elixir-lang-core" group. >>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>> an email to [email protected]. >>>>> To view this discussion on the web visit >>>>> https://groups.google.com/d/msgid/elixir-lang-core/CACFi_YOGbfSBn4jYJ4djPwVeuwxYu0cWt5Mja62f%3DWmZKZ7CUQ%40mail.gmail.com >>>>> <https://groups.google.com/d/msgid/elixir-lang-core/CACFi_YOGbfSBn4jYJ4djPwVeuwxYu0cWt5Mja62f%3DWmZKZ7CUQ%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>>> . >>>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "elixir-lang-core" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to [email protected]. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4JYnayA0QnDTqwJrYUT4b8tokk8bpD2UD9%2BGP0LX%3DgDQw%40mail.gmail.com >>>> <https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4JYnayA0QnDTqwJrYUT4b8tokk8bpD2UD9%2BGP0LX%3DgDQw%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>> . >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "elixir-lang-core" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/elixir-lang-core/l5mjnis5.050a125c-ff42-494a-a8c5-27e5415c052e%40we.are.superhuman.com >>> <https://groups.google.com/d/msgid/elixir-lang-core/l5mjnis5.050a125c-ff42-494a-a8c5-27e5415c052e%40we.are.superhuman.com?utm_medium=email&utm_source=footer> >>> . >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "elixir-lang-core" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/elixir-lang-core/CACFi_YNrjEfL%2BU%3D8NG8CkuREk%2BGt8wE-1thhdftzGVJ9tX2gSg%40mail.gmail.com >> <https://groups.google.com/d/msgid/elixir-lang-core/CACFi_YNrjEfL%2BU%3D8NG8CkuREk%2BGt8wE-1thhdftzGVJ9tX2gSg%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> > -- > You received this message because you are subscribed to the Google Groups > "elixir-lang-core" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/elixir-lang-core/l5mvi03t.3d49c354-235f-496b-92aa-52ccbb74dcba%40we.are.superhuman.com > <https://groups.google.com/d/msgid/elixir-lang-core/l5mvi03t.3d49c354-235f-496b-92aa-52ccbb74dcba%40we.are.superhuman.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "elixir-lang-core" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/CACFi_YPX-51XWfqm02X6MXL04Yv9_T71oUeLrBJcgRE-W8zi2A%40mail.gmail.com.
