Re: Negative occur

Re: Negative occur

[Ted Zlatanov]

On Wed, 28 Nov 2007 14:52:15 -0800 "Drew Adams" <drew.adams@oracle.com> wrote: 

>> >> > You could try running "occur" with the pattern "^" (which matches
>> >> > every line), then prune the results with M-x delete-matching-lines
DA> RET

DA> [spamfilteraccount suggested that Emacs should have this as part of
DA> `occur'...]

DA> I realize that your suggestion is that this be added to
DA> Emacs. I agree. FYI - In Icicles, just do this: C-' foobar C-~
DA> That shows and lets you visit all lines that do not match the
DA> regexp "foobar".
>> 
>> Both solutions will be slower on a large buffer than they should be.

DA> What does "slower than they should be" mean? How slow should they be? How
DA> slow are they in fact? How large is a large buffer? How do you judge that
DA> "they" (two totally different approaches and implementations) are slower
DA> than they should be?

I'm certain that creating an *occur* buffer on every line of a 100+ MB
buffer and then removing most of them compares poorly in memory usage
and CPU usage to just matching what you need from it.  It's a very
suboptimal approach whose only advantage is that it doesn't require
changes to any internal logic.  A parallel would be (using `sort'
instead of `cat' to account for Emacs' memory usage):

sort file | grep x
grep x file | sort

>> A real inversion parameter, either as a predicate function or a variable,
>> passed lexically or as a parameter to the occur-engine function call, is
>> necessary.

DA> Necessary? For what? Why necessary? These are generalizations that don't
DA> help.

Necessary to implement the solution in such a way that it will satisfy
both the OP and future needs for tuning the occur results.  I'm not
talking about Icicles (that's why I mentioned occur-1 and occur-engine
originally), sorry if I didn't state that clearly.  I just thought that
since you recommended the filter-later approach, Icicles didn't support
predicates, so it made sense to follow up to you.

DA> Your statements are vague, but I'm guessing that what you're really trying
DA> to say is that it is often more efficient to apply a predicate earlier
DA> rather than later (filter promotion), which is true.

Sure.  Reduce the search results as early as possible, as in my earlier
example of sort/grep usage.

DA> The Icicles approach is designed for interactive use, which is why it
DA> emphasises changing search patterns (and predicates) on the fly. It works
DA> fine with any buffers I've ever used, some of which are pretty darn big.
DA> (How big is big? I just searched a 19MB buffer with no effect on
DA> interactivity.)

DA> As always, the usefulness of a tool depends on what you use it for. If you
DA> want to search a 5 terabyte file, then interactivity might suffer with some
DA> approaches (depending on your hardware... and, especially, depending on your
DA> regexp). But, as always, the devil is in the details.

I can see that between a O(n) and O(n log(n)) algorithm for small data
sets, but when the difference is that one approach copies every line and
the other doesn't, while they achieve the same result, it literally
bothers me to recommend the former approach just because the API doesn't
support the latter.  So I'll propose the API change to emacs-devel.

As for hardware, I maintain an Emacs Maemo port, which is for the Nokia
770/800/810 tablets that run GNU/Linux.  There is little memory
available and the CPU is slow, so copying a large buffer unnecessarily
would be terrible for the user experience.

Ted

RE: Negative occur

[Drew Adams]

> I'm not talking about Icicles (that's why I mentioned occur-1
> and occur-engine originally), sorry if I didn't state that
> clearly.  I just thought that since you recommended the
> filter-later approach, Icicles didn't support
> predicates, so it made sense to follow up to you.

A misunderstanding, then. I said "In Icicles, just do this..." and you
replied "Both solutions will be slower...".

I didn't recommend any filter-later approach.

In fact, I said "I realize that [spamfilter's] suggestion is that this be
added to Emacs. I agree.". By which I meant that it makes sense to let
`occur' do this itself. And in an efficient way - the first time around (not
via an after-the-fact filter).

> DA> As always, the usefulness of a tool depends on what you use
> DA> it for. If you want to search a 5 terabyte file, then
> DA> interactivity might suffer with some approaches (depending
> DA> on your hardware... and, especially, depending on your
> DA> regexp). But, as always, the devil is in the details.
>
> I can see that between a O(n) and O(n log(n)) algorithm for small data
> sets, but when the difference is that one approach copies every line and
> the other doesn't, while they achieve the same result, it literally
> bothers me to recommend the former approach just because the API doesn't
> support the latter.  So I'll propose the API change to emacs-devel.

Makes sense to me. I thought that Tamas (oops, spamfilter) was already
suggesting that. If `occur' is made to handle non-matches, it should
certainly do that efficiently.

Re: Negative occur

[spamfilteraccount]

On Nov 29, 6:25 pm, "Drew Adams" <drew.ad...@oracle.com> wrote:
>
> Makes sense to me. I thought that Tamas (oops, spamfilter) was already
> suggesting that.

It's okay to use my name. :)))

I did something wrong when setting up my Google Groups account ages
ago, and I just don't care enough to fix it.

Re: Negative occur

[Mathias Dahl]

"spamfilteraccount@gmail.com" <spamfilteraccount@gmail.com> writes:

>> Makes sense to me. I thought that Tamas (oops, spamfilter) was already
>> suggesting that.
>
> It's okay to use my name. :)))
>
> I did something wrong when setting up my Google Groups account ages
> ago, and I just don't care enough to fix it.

It's OK Tamas.  At first I though it was annoying, some spammer coming
to the list, but then I found you were really just a nice guy, so now
I think it's just cute... :)

Re: Negative occur

[Ted Zlatanov]

On Wed, 28 Nov 2007 09:03:17 -0800 "Drew Adams" <drew.adams@oracle.com> wrote: 

DA> On Wed, 28 Nov 2007 11:21:43 +0100 David Kastrup <dak@gnu.org> wrote: 
>> > You could try running "occur" with the pattern "^" (which matches
>> > every line), then prune the results with M-x delete-matching-lines RET

DA> I realize that your suggestion is that this be added to Emacs. I agree.

DA> FYI - In Icicles, just do this:  C-' foobar C-~

DA> That shows and lets you visit all lines that do not match the regexp
DA> "foobar". `C-'' is `icicle-occur'. `C-~' complements the current set of
DA> matches.

Both solutions will be slower on a large buffer than they should be.  A
real inversion parameter, either as a predicate function or a variable,
passed lexically or as a parameter to the occur-engine function call, is
necessary.  A predicate function is probably best as it can express
transformations more complex than identity and negation.

Ted

RE: Negative occur

[Drew Adams]

> >> > You could try running "occur" with the pattern "^" (which matches
> >> > every line), then prune the results with M-x delete-matching-lines
RET

[spamfilteraccount suggested that Emacs should have this as part of
`occur'...]

> DA> I realize that your suggestion is that this be added to
> DA> Emacs. I agree. FYI - In Icicles, just do this: C-' foobar C-~
> DA> That shows and lets you visit all lines that do not match the
> DA> regexp "foobar".
>
> Both solutions will be slower on a large buffer than they should be.

What does "slower than they should be" mean? How slow should they be? How
slow are they in fact? How large is a large buffer? How do you judge that
"they" (two totally different approaches and implementations) are slower
than they should be?

> A real inversion parameter, either as a predicate function or a variable,
> passed lexically or as a parameter to the occur-engine function call, is
> necessary.

Necessary? For what? Why necessary? These are generalizations that don't
help.

Despite the name, `icicle-occur' (C-') doesn't even use "the occur-engine".
If you are suggesting that Emacs `occur' should let you pass a predicate and
incorporate it in a single search pass, that might be worthwhile, but it is
in any case irrelevant for `icicle-occur.

> A predicate function is probably best as it can express
> transformations more complex than identity and negation.

In Icicles, you can also apply a predicate for searching, and you can do
that on the fly too. You can combine any number of predicates that way. You
can mix regexps and predicates for searching. See
http://www.emacswiki.org/cgi-bin/wiki/Icicles_-_Progressive_Completion#Predi
cates.

Your statements are vague, but I'm guessing that what you're really trying
to say is that it is often more efficient to apply a predicate earlier
rather than later (filter promotion), which is true.

Icicles also lets you do that, BTW, to define your own Icicles search
command that incorporates a predicate from the outset (as opposed to using
it as a filter afterward). And this too can be mixed with regexp searching.

An example of this are the definitions of the Icicles Imenu commands that
let you browse definitions of Emacs commands only or non-interactive
functions only: an Imenu regexp to recognize function definitions is
combined with a `commandp' test.
http://www.emacswiki.org/cgi-bin/wiki/Icicles_-_Other_Search_Commands#Define
SearchCommands

However, the real question about efficiency is whether something is
efficient _enough_.

The Icicles approach is designed for interactive use, which is why it
emphasises changing search patterns (and predicates) on the fly. It works
fine with any buffers I've ever used, some of which are pretty darn big.
(How big is big? I just searched a 19MB buffer with no effect on
interactivity.)

As always, the usefulness of a tool depends on what you use it for. If you
want to search a 5 terabyte file, then interactivity might suffer with some
approaches (depending on your hardware... and, especially, depending on your
regexp). But, as always, the devil is in the details.

Negative occur

[spamfilteraccount]

Is there a command like occur which shows non-matching lines? It would
come in handy for me for the work I'm doing.

It's a useful a feature and not hard to implement, so I'm sure it's
already in Emacs in some form only I'm overlooking it.

Re: Negative occur

[David Kastrup]

"spamfilteraccount@gmail.com" <spamfilteraccount@gmail.com> writes:

> Is there a command like occur which shows non-matching lines? It would
> come in handy for me for the work I'm doing.
>
> It's a useful a feature and not hard to implement, so I'm sure it's
> already in Emacs in some form only I'm overlooking it.

You could try running "occur" with the pattern "^" (which matches
every line), then prune the results with M-x delete-matching-lines RET

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Negative occur

[spamfilteraccount]

On Nov 28, 11:21 am, David Kastrup <d...@gnu.org> wrote:
> "spamfilteracco...@gmail.com" <spamfilteracco...@gmail.com> writes:
> > Is there a command like occur which shows non-matching lines? It would
> > come in handy for me for the work I'm doing.
>
> > It's a useful a feature and not hard to implement, so I'm sure it's
> > already in Emacs in some form only I'm overlooking it.
>
> You could try running "occur" with the pattern "^" (which matches
> every line), then prune the results with M-x delete-matching-lines RET
>

Yep, there are workarounds. :)

But it seems a very basic feature, so I'd be surprised if Emacs didn't
have it.

We have keep-lines and flush-lines after all, so it would be logical
to have the same for occur.

RE: Negative occur

[Drew Adams]

> > > Is there a command like occur which shows non-matching lines? It would
> > > come in handy for me for the work I'm doing.
> >
> > > It's a useful a feature and not hard to implement, so I'm sure it's
> > > already in Emacs in some form only I'm overlooking it.
> >
> > You could try running "occur" with the pattern "^" (which matches
> > every line), then prune the results with M-x delete-matching-lines RET
>
> Yep, there are workarounds. :) But it seems a very basic feature,
> so I'd be surprised if Emacs didn't have it. We have keep-lines
> and flush-lines after all, so it would be logical to have the
> same for occur.

I realize that your suggestion is that this be added to Emacs. I agree.

FYI - In Icicles, just do this:  C-' foobar C-~

That shows and lets you visit all lines that do not match the regexp
"foobar". `C-'' is `icicle-occur'. `C-~' complements the current set of
matches.

You can also then match additional regexps, dynamically, just by typing
them, separated by `S-SPC' or `C-~'. `S-SPC' means AND (set intersection)
and `C-~' means AND NOT (set complement). Each applies to the current set of
matches. Example:

 C-' foobar C-~ toto S-SPC titi C-~ tata

That shows and lets you visit all lines that do not contain "foobar", do
contain "toto", do not contain "titi", and do contain "tata". You get the
idea: you can get what you want by progressively narrowing the search space.

http://www.emacswiki.org/cgi-bin/wiki/Icicles_-_Search_Commands%2c_Overview

Re: Negative occur

[spamfilteraccount]

On Nov 28, 11:53 am, "spamfilteracco...@gmail.com"
<spamfilteracco...@gmail.com> wrote:
> On Nov 28, 11:21 am, David Kastrup <d...@gnu.org> wrote:
>
> > "spamfilteracco...@gmail.com" <spamfilteracco...@gmail.com> writes:
> > > Is there a command like occur which shows non-matching lines? It would
> > > come in handy for me for the work I'm doing.
>
> > > It's a useful a feature and not hard to implement, so I'm sure it's
> > > already in Emacs in some form only I'm overlooking it.
>
> > You could try running "occur" with the pattern "^" (which matches
> > every line), then prune the results with M-x delete-matching-lines RET
>
> Yep, there are workarounds. :)

Here's a naive implementation of noccur I made for myself:

(defun noccur ()
  (interactive)
  (let ((orig-re-search-forward (symbol-function 're-search-forward)))
    (fset 're-search-forward 'noccur-re-search-forward)
    (unwind-protect
        (call-interactively 'occur)
      (fset 're-search-forward orig-re-search-forward))))


(defun noccur-re-search-forward (regexp bound noerror &optional count)
  (unless (eq (aref regexp 0) ?^)
    (setq regexp (concat ".*" regexp)))

  (while (and (not (eobp))
              (looking-at regexp))
    (forward-line 1))

  (if (eobp)
      nil
    (set-match-data (list (line-beginning-position)
                          (line-end-position)))
    (line-end-position)))


(provide 'nocccur)