Searching question

This is a discussion on Searching question within the C++ Programming forums, part of the General Programming Boards category; Hi: I have been working on a project which requires searching through the rows of a matrix (of integers) for ...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    5

    Searching question

    Hi:

    I have been working on a project which requires searching through the rows of a matrix (of integers) for a particular row (this is in C++). Currently, I have each row in a binary search tree (using a lexicographic ordering on the rows) - I am wondering if there is a faster way of searching the rows. The < operator runs in O(n), so I was wondering if there are any other orderings/containers which would improve on this. (As far as I am aware, the tree is balanced.)

    Thanks,
    gfdsa

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    What exactly is the problem? And how are you certain your tree is balanced?

  3. #3
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Only 5 posts and already being condescending, you are my favorite new member What I meant by "what is the problem?" is things seem to sound very smooth as it is. Are you having general performance issues? If you are, you can always create index to reference logical places in your tree (thus allowing you to skip ahead... though I don't recommend this if things are going smooth now since you need to do a fair amount of logic to implement the look up tables).

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    5
    "already being condescending"
    Sorry, that wasn't my intention - I misunderstood what you meant.

    The problem is that I have a tree with around k^(k-2) elements (each is an array of length k), which is hard to handle for even small values of k, so I am looking for better algorithms.

    gfdsa
    Last edited by gfdsa; 04-25-2008 at 09:07 PM.

  5. #5
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Ok, so here is a series of question that could perhaps prevent you from posting code. Usually your tree will perform at around O(n) if the tree is needing to scan as many branches as there are entries, right? So that would lead one to believe that balance is not existing.

    How are you searching for your data? Is it possible your actual algorithm that traverses the tree is searching areas where it need not go? I remember writing a compression algorithm once that would use a very large BSP to do a statistical analysis of the frequency of data, and it ran very quickly.

    If all else fails, just post your code. Things have become messy over the years, I've noticed. The best way to post code is in the form of an attachment. Pseudo code is so hard to help people with. And I hate reading code off the forums.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 01:14 PM
  2. Design layer question
    By mdoland in forum C# Programming
    Replies: 0
    Last Post: 10-19-2007, 05:22 AM
  3. Exam Question - Possible Mistake?
    By Richie T in forum C++ Programming
    Replies: 15
    Last Post: 05-08-2006, 04:44 PM
  4. File Searching with _findfirst and _findnext
    By l WolfPac l in forum C Programming
    Replies: 1
    Last Post: 01-03-2003, 02:55 AM
  5. what does this warningmean???
    By kreyes in forum C Programming
    Replies: 5
    Last Post: 03-04-2002, 07:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21