Skip to content
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

Collection constructor is very slow with large lists #609

Closed
hsolbrig opened this issue Mar 17, 2016 · 2 comments
Closed

Collection constructor is very slow with large lists #609

hsolbrig opened this issue Mar 17, 2016 · 2 comments

Comments

@hsolbrig
Copy link
Contributor

The collection constructor uses the append method, which iterates to the end of the list for every addition. This results in a n! performance. Propose replacing:

    for item in seq:
         self.append(item)

with:

    if seq:
        nxt = self.uri
        for item in seq:
            graph.add((nxt, RDF.first, item))
            nxt2 = BNode()
            graph.add((nxt, RDF.rest, nxt2))
            nxt = nxt2
        graph.add((nxt, RDF.first, RDF.nil))

in the constructor

@joernhees
Copy link
Member

it's O(n^2), but i agree that it's unnecessary... if you make a pull request, i'll accept it.

@joernhees joernhees added enhancement New feature or request performance labels Mar 18, 2016
@joernhees joernhees added this to the rdflib 4.2.2 milestone Mar 18, 2016
gromgull added a commit that referenced this issue Jan 19, 2017
… items.

Fixes #609

As a bonus adds a `graph.collection` convenience method for creating collections
gromgull added a commit that referenced this issue Jan 19, 2017
… items.

Fixes #609

As a bonus adds a `graph.collection` convenience method for creating collections
gromgull added a commit that referenced this issue Jan 19, 2017
… items.

Fixes #609

As a bonus adds a `graph.collection` convenience method for creating collections
@gromgull
Copy link
Member

I went for a fix without the _end caching issues. Now there is a __iadd__ method that lets you do my_collection += [ Literal(1), Literal(2) ] and this will be efficient. Repeat calls to append remain inefficient, but this is safer!

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

No branches or pull requests

3 participants