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.

Sign up for GitHub

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

Jump to bottom

perf(index): hash-based type lookup #58

Open

cmdoret opened this issue Aug 26, 2024 · 0 comments

Member

cmdoret commented Aug 26, 2024 •

edited

Loading

The new TypeIndex struct introduced in #57 is as follows:

{
  "types": ["type1_uri", "type2_uri"],
  "map": {
    "hash(subject1_uri)": ["usize(type1_index)"],
    "hash(subject2_uri)": ["usize(type2_index)", "usize(type1_index)"],
   "..."
  }
}

While it is compact, type lookup is O(n*m) where n is #types and m is #types-per-subject.

Objective: add a (non-serialized) type_indices field to get O(1) lookup as suggested in #57 (comment)

cmdoret mentioned this issue

perf(index): lightweight structure #57

Merged

7 tasks

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