New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

pandoc uses nub #1022

Closed
nh2 opened this Issue Oct 11, 2013 · 9 comments

Comments

Projects
None yet
4 participants
@nh2

nh2 commented Oct 11, 2013

https://github.com/nh2/haskell-ordnub

Only a single nub appearance though - great!

It's in varListToJSON in Text.Pandoc.Templates.

@nh2

This comment has been minimized.

Show comment
Hide comment
@nh2

nh2 Oct 11, 2013

Other n² uses I found:

  • \\ is used in src/Text/Pandoc/Writers/LaTeX.hs
  • intersect is used in src/Text/Pandoc/Writers/Org.hs and src/Text/Pandoc/Writers/MediaWiki.hs

nh2 commented Oct 11, 2013

Other n² uses I found:

  • \\ is used in src/Text/Pandoc/Writers/LaTeX.hs
  • intersect is used in src/Text/Pandoc/Writers/Org.hs and src/Text/Pandoc/Writers/MediaWiki.hs
@dashed

This comment has been minimized.

Show comment
Hide comment
@dashed

dashed Oct 12, 2013

To clarify, are you suggesting to use ordnub over nub?

dashed commented Oct 12, 2013

To clarify, are you suggesting to use ordnub over nub?

@nh2

This comment has been minimized.

Show comment
Hide comment
@nh2

nh2 Oct 12, 2013

To clarify, are you suggesting to use ordnub over nub?

Yes, or Set.toList . Set.fromList if the order does not matter (ordNub takes care to produce the same order as nub).

nh2 commented Oct 12, 2013

To clarify, are you suggesting to use ordnub over nub?

Yes, or Set.toList . Set.fromList if the order does not matter (ordNub takes care to produce the same order as nub).

@jgm

This comment has been minimized.

Show comment
Hide comment
@jgm

jgm Oct 12, 2013

Owner

It's probably not worth making the change in this case. Lists of
variables specified on the command line are almost always short.
It's hard to imagine a real case where the n^2 behavior causes
problems here.

Owner

jgm commented Oct 12, 2013

It's probably not worth making the change in this case. Lists of
variables specified on the command line are almost always short.
It's hard to imagine a real case where the n^2 behavior causes
problems here.

@nh2

This comment has been minimized.

Show comment
Hide comment
@nh2

nh2 Oct 12, 2013

Why keep the n² algorithm when the n_log n algorithm is simple and faster in *all_ cases (even for singleton lists)?

Using nub is just bad practice: In my opinion, already the fact that you have to think about "is the list long or not" justifies replacing it.

nh2 commented Oct 12, 2013

Why keep the n² algorithm when the n_log n algorithm is simple and faster in *all_ cases (even for singleton lists)?

Using nub is just bad practice: In my opinion, already the fact that you have to think about "is the list long or not" justifies replacing it.

@nougad

This comment has been minimized.

Show comment
Hide comment
@nougad

nougad Oct 12, 2013

Contributor

It takes me about 3 minutes to compile your library and the required dependencies on my system. And the time saving is around 1ms (assuming 10 parameters according to your benchmark) per call. So I need to call pandoc 180000 times (without recompiling it) to make any earnings from your suggestion. NOT including the time to change the code, recompile, test, ...

From a theoretical perspective it makes sense to always use a log(n)*n instead n^2 - but definitely not in this practical use case.

I think pandoc has has more important thinks to do

Contributor

nougad commented Oct 12, 2013

It takes me about 3 minutes to compile your library and the required dependencies on my system. And the time saving is around 1ms (assuming 10 parameters according to your benchmark) per call. So I need to call pandoc 180000 times (without recompiling it) to make any earnings from your suggestion. NOT including the time to change the code, recompile, test, ...

From a theoretical perspective it makes sense to always use a log(n)*n instead n^2 - but definitely not in this practical use case.

I think pandoc has has more important thinks to do

@nh2

This comment has been minimized.

Show comment
Hide comment
@nh2

nh2 Oct 12, 2013

It takes me about 3 minutes to compile your library and the required dependencies

Which library? https://github.com/nh2/haskell-ordnub is not a library - it is a benchmark suite to compare the performance of various nub implementations... does that make sense?

nh2 commented Oct 12, 2013

It takes me about 3 minutes to compile your library and the required dependencies

Which library? https://github.com/nh2/haskell-ordnub is not a library - it is a benchmark suite to compare the performance of various nub implementations... does that make sense?

@dashed

This comment has been minimized.

Show comment
Hide comment
@dashed

dashed Oct 12, 2013

Although it's great that you've found a better time complexity for nub, this seems to be a classic case of premature optimization. Anyone needing to use a huge list of variables may need to fork the pandoc project to customize it to their needs.

dashed commented Oct 12, 2013

Although it's great that you've found a better time complexity for nub, this seems to be a classic case of premature optimization. Anyone needing to use a huge list of variables may need to fork the pandoc project to customize it to their needs.

@jgm jgm closed this in 9b4e772 Jun 3, 2014

@nh2

This comment has been minimized.

Show comment
Hide comment
@nh2

nh2 commented Jun 3, 2014

Yay!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment