To jest mój główny algorytm wyszukiwania wielu elementów przy użyciu funkcji binarnej i oddzielnej. Potrzebuję kogoś, kto zmieni moje podejście.

private int Multisearch(TYPE key){

        int ind = binarySearchComparator(key);


     // If element is not present 
        if (ind == -1) 
            return -1; 

        // Count elements on left side. 
        int count = 1; 
        int left = ind - 1; 
        int i = 1;
        while (left >= 0 && (comparator.compare(list[left], key)) == 0) 
        { 
            lol[i] = list[left];      // store left found elements in array here  
            i++;
            count++; 
            left--; 

        } 

        // Count elements  
        // on right side. 
        int right = ind + 1; 

        try{


        while (right < list.length && (comparator.compare(list[right], key)) == 0) 
        { 
            lol[i] = list[right];      // store right found elements in array here  
            i++;
            count++; 
            right++; 



        } 

        }catch(Exception e){

        }


        return count; 
    }



private int binarySearchComparator(TYPE key) {
        int low = 0;
        int high = count - 1;

        while (low <= high) {

            int mid = (low + high) / 2 ;
            TYPE midVal = list[mid];
            int cmp = comparator.compare(midVal, key);
            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }

        return -1;  // key not found.
    }

Powyższy kod to moje podejście i moja kopia zapasowa. Chcę, żebyście używali wyszukiwania binarnego do wyszukiwania wielu elementów i przechowywania ich gdzieś w celu wyświetlenia użytkownikowi, gdy użytkownik filtruje elementy według płci, a funkcja wyszukiwania binarnego wyszuka elementy „Mężczyzna” i wyświetli je wszystkie dla użytkownika.

Potrzebuję go do wyszukiwania wielu elementów i wyświetlania / przechowywania ich w innym miejscu, aby wyświetlić je użytkownikowi.

Nawiasem mówiąc, to jest jak funkcja filtrująca, jeśli jakakolwiek dusza jest w stanie mi pomóc. Będę bardzo wdzięczny!

Cóż, jeśli rzeczywiście możesz policzyć wystąpienie tego samego przedmiotu / obiektu i zapisać je do późniejszego wyświetlenia. Będę nawet bardzo wdzięczny za takie podejście! Proszę, pokaż mi jak! Dzięki!

Interfejs listy sortowanej

public interface SortedListInterface <TYPE extends Comparable<TYPE>> {


    public boolean add(TYPE element);


    public TYPE get(int index);


    public int search(TYPE element);


    public TYPE remove(int index);


    public void clear();




public int getLength();


public boolean isEmpty();


public boolean isFull();

}

Klasa SearchComparator

public class MobileSearch implements Comparator<Student>{


    private String type;

    public void setType(String type) {
        this.type = type;
    }

    public String getType() {
        return type;
    }




    @Override
    public int compare(Student student1, Student student2) {


        int result = 0;



        if(this.type.equals("mobile")){
            result = student1.getMobileNo().compareTo(student2.getMobileNo());
            System.out.print(result+"mobile");
        }

        else if(this.type.equals("name")){
            result = student1.getName().getFullName().compareTo(student2.getName().getFullName());
             System.out.println(result+"name");
        }

        else if(this.type.equals("group")){

                 result = student1.getGroup().compareTo(student2.getGroup());
                 System.out.print(result+"group");

             }



        return result;
    }

}

Implementacja SortedArrayList

public class SortedArrayList<TYPE extends Comparable<TYPE>> implements SortedListInterface<TYPE>{

  //Data Types  

  private TYPE[] list;
  private int length;
  private static final int SIZE = 10;

  private Comparator<? super TYPE> comparator;
  private int count;


  @SuppressWarnings("unchecked")
    public SortedArrayList(Comparator<? super TYPE> c) {
        comparator = c;
        list = (TYPE[]) new Comparable[SIZE]; // No way to verify that 'list' only contains instances of 'T'.

        /* NOTE: Following is not allowed.
        list = new T[SIZE]; // Cannot create a generic array of T
        */
    }




  // Constructors

  public SortedArrayList() {
    this(SIZE);
  }

  public SortedArrayList(int size) {
    length = 0;
    list = (TYPE[]) new Comparable[SIZE]; // an array of instances of a class implementing Comparable interface and able to use compareto method but its overidden instead
  }



  // Setter & Getters

  @Override
  public int getLength() {
    return length;
  }

  @Override
  public boolean isEmpty() {
    return length == 0;
  }

  @Override
  public boolean isFull() {
    return false;
  }

  @Override
  public void clear() {
    length = 0;
  }


  // Array Expansion

  private boolean isArrayFull() {
    return length == list.length;
  }

  private void expandArray() {
    TYPE[] oldList = list;
    int oldSize = oldList.length;

    list = (TYPE[]) new Object[2 * oldSize];

    for (int i = 0; i < oldSize; i++) // copy old array elements into new array elements
      list[i] = oldList[i];

  }




  // ADT METHODs


  // Add New Elements Function


  @Override
//    public boolean add(TYPE element) {
//        int i = 0;
//
//        while (i < length && element.compareTo(list[i]) > 0) // return 0 with equal , return more than 1 if element larger than list[i] , return -1 if less
//        {
//            i++;
//        }
//
//        makeRoom(i + 1);
//        list[i] = element;
//        length++;
//        return true;
//    }


  public boolean add(TYPE element) {

        boolean result = false;
        if (count == 0) {
            list[0] = element;
            count = 1;
            result = true;
        }
        else {
            if (!isFull()) {
                int i = 0;
                while (list[i] != null) {
                    if (element.compareTo(list[i]) < 0) {
                        break;
                    }
                    i++;
                }
                if (list[i] != null) {
                    for (int j = count - 1; j >= i; j--) {
                        list[j + 1] = list[j];
                    }
                }
                list[i] = element;
                count++;
                result = true;
            }
        }
        return result;
    }


  private void makeRoom(int index) {  // accepts given index
    int newIndex = index - 1;
    int lastIndex = length - 1;

    for (int i = lastIndex; i >= newIndex; i--) 
      list[i + 1] = list[i];

  }



  //Remove Elements Function

  @Override
  public TYPE remove(int index) {  // accepts given index

    TYPE result = null;

    if ( index >= 1 && index <= length ) {

      result = list[index - 1];

      if (index < length) 
        removeGap(index);

      length--;
    }

    return result;
  }

  private void removeGap(int index) { // accepts given index and remove the gap where the element its removed

    int removedIndex = index - 1;
    int lastIndex = length - 1;

    for (int i = removedIndex; i < lastIndex; i++) 
      list[i] = list[i + 1]; // shifts elements back to remove the gap

  }


  // Get Element

  @Override
  public TYPE get(int index) { // accepts given index and return the object

    TYPE object = null;

    if ( index >= 1 && index <= length) 
      object = list[index - 1];

    return object;

  }


  // Search Algorithms

  @Override
// public boolean search(TYPE element) {
//    boolean found = false;
//    
//    int lo = 0;
//    int hi = count - 1;
//    
//    while (lo <= hi) {
//        int mid = (lo + hi) / 2;
//        if (list[mid].compareTo(element) < 0) {
//            lo = mid + 1;
//        }
//        else if (list[mid].compareTo(element) > 0) {
//            hi = mid - 1;
//        }
//        else if (list[mid].compareTo(element) == 0) {
//            found = true;
//            break;
//        }
//          return found
//    }

  public int search(TYPE element) {

            return exponentialSearch(element);

    }



  private boolean binarySearchComparable(TYPE element) {
        boolean found = false;
        int lo = 0;
        int hi = count - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (list[mid].compareTo(element) < 0) {
                lo = mid + 1;
            }
            else if (list[mid].compareTo(element) > 0) {
                hi = mid - 1;
            }
            else if (list[mid].compareTo(element) == 0) {
                found = true;
                break;
            }
        }
        System.out.print("Single");
        return found;
    }


    private int exponentialSearch(TYPE key){

        int ind = binarySearchComparator(key);


     // If element is not present 
        if (ind == -1) 
            return -1; 

        // Count elements on left side. 
        int count = 1; 
        int left = ind - 1; 
        int i = 1;
        while (left >= 0 && (comparator.compare(list[left], key)) == 0) 
        { 
//            lol[i] = list[left];
            System.out.println(left+"lefttest");
            i++;
            count++; 
            left--; 

        } 

        // Count elements  
        // on right side. 
        int right = ind + 1; 

        try{


        while (right < list.length && (comparator.compare(list[right], key)) == 0) 
        { 
            System.out.println(right+"righttest");
//            lol[i] = arr[right];
            i++;
            count++; 
            right++; 



        } 

        }catch(Exception e){

        }


        return count; 
    }

    private int binarySearchComparator(TYPE key) {
        int low = 0;
        int high = count - 1;

        while (low <= high) {

            int mid = (low + high) / 2 ;
            TYPE midVal = list[mid];
            int cmp = comparator.compare(midVal, key);
            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }

        return -1;  // key not found.
    }













  //To String Method

  @Override
  public String toString() {

    String result = "";

    for (int i = 0; i < count; i++) 
      result += list[i] + "\n";

    return result;

  }



}

Klasa nazw

public class Name {

    // Data Types

    private String firstName;
    private String lastName;


    // Constructors

    public Name() {
    }

    public Name(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    // setter

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

    public void setLastName(String lastName) {
        this.lastName = lastName;
    }

    // getter

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public String getFullName(){
        return firstName + " " + lastName;
    }

    @Override
    public String toString() {
        return "Name{" + "firstName=" + firstName + ", lastName=" + lastName + '}';
    }







}

klasa studentów

public class Student implements Comparable<Student>{


   // Data Types 

   private String studID; 
   private Name name;
   private String gender;
   private String icNo;
   private String mobileNo;
   private Course course;
   private String group;
   private String dOB;


   // Constructors

   public Student() {
   }


    public Student(String studID, Name name, String gender, String icNo, String mobileNo, Course course, String group, String dOB) {
        this.studID = studID;
        this.name = name;
        this.gender = gender;
        this.icNo = icNo;
        this.mobileNo = mobileNo;
        this.course = course;
        this.group = group;
        this.dOB = dOB;
    }



   public Student(Name name) {
        this.name = name;
    }


   // setter


    public void setStudID(String studID) {
        this.studID = studID;
    }

   public void setName(Name name) {
        this.name = name;
    }

    public void setGender(String gender) {
        this.gender = gender;
    }

    public void setIcNo(String icNo) {
        this.icNo = icNo;
    }

    public void setMobileNo(String mobileNo) {
        this.mobileNo = mobileNo;
    }

    public void setCourse(Course course) {
        this.course = course;
    }

    public void setGroup(String group) {
        this.group = group;
    }

    public void setdOB(String dOB) {
        this.dOB = dOB;
    }


    // getter

    public String getStudID() {
        return studID;
    }

    public Name getName() {
        return name;
    }

    public String getGender() {
        return gender;
    }

    public String getIcNo() {
        return icNo;
    }

    public String getMobileNo() {
        return mobileNo;
    }

    public Course getCourse() {
        return course;
    }

    public String getGroup() {
        return group;
    }

    public String getdOB() {
        return dOB;
    }

    @Override
    public String toString() {
        return "Student{" + "name=" + name + ", gender=" + gender + ", icNo=" + icNo + ", mobileNo=" + mobileNo + ", course=" + course + ", group=" + group + ", dOB=" + dOB + '}';
    }


   @Override
   public int compareTo(Student object) { // Sort according to name if name same then sort according to gender and so on.

    int c = this.name.getFullName().compareTo(object.getName().getFullName());

    if(c == 0)
        c = this.gender.compareTo(object.getGender()); 

    if(c == 0)
        c = this.icNo.compareTo(object.getIcNo());  

    if(c == 0)
        c = this.mobileNo.compareTo(object.getMobileNo());

    if(c == 0)
        c = this.group.compareTo(object.getGroup());

    if(c == 0)
        c = this.dOB.compareTo(object.getdOB());

    return c;

  }

   public static Student[] sort(Student[] object,String category){


       Student[] array;

       if(category.equals("ID")){
         for (int i=1; i < object.length; i++) {
           for(int j = 0 ; j < object.length - i ; j++)
               if( (object[j].getGender().compareTo(object[j+1].getGender())) > 0 ){
                    Student lol = object[j];
                    object[j] = object[j+1];
                    object[j+1] = lol;
              }
       }



   }
        array = object;
       return array;
  }


}

Klasa kursu

public class Course {


    // Data Types

    private String courseCode;
    private String courseName;
    private double courseFee;


    // Constructors

    public Course() {
    }

    public Course(String courseCode, String courseName, double courseFee) {
        this.courseCode = courseCode;
        this.courseName = courseName;
        this.courseFee = courseFee;
    }

    // setter

    public void setCourseCode(String courseCode) {
        this.courseCode = courseCode;
    }

    public void setCourseName(String courseName) {
        this.courseName = courseName;
    }

    public void setCourseFee(double courseFee) {
        this.courseFee = courseFee;
    }


    // getter

    public String getCourseCode() {
        return courseCode;
    }

    public String getCourseName() {
        return courseName;
    }

    public double getCourseFee() {
        return courseFee;
    }

    @Override
    public String toString() {
        return "CourseCode = " + courseCode + "Course Name = " + courseName + "Course Fee = " + courseFee;
    }




}
-2
Cash- 19 listopad 2019, 17:55

1 odpowiedź

Jeśli Twoje dane są już posortowane, nie uzyskasz szybszego wyniku niż wyszukiwanie binarne O (log n) . Jeśli jest więcej niż jedno dopasowanie, znajdź jedno dopasowanie, a następnie wykonaj iterację do przodu (do momentu, gdy nie zostanie znalezionych więcej dopasowań) i do tyłu (aż nie zostanie znalezionych więcej dopasowań), aby uzyskać wszystkie dopasowania. dopasowania, możesz zastąpić iterującą część ponownie wyszukiwaniem binarnym pierwszego / ostatniego pasującego elementu. Zmniejszyłoby to złożoność do O (n) bez względu na liczbę dopasowań)

To wymaga O (log n) + O (#matches)

Jeśli to nie jest wystarczająco szybkie, spróbuj sprofilować swoją implementację, aby znaleźć wąskie gardło, w którym dalsze próby optymalizacji mają największy sens.

0
MrSmith42 20 listopad 2019, 14:01
Czy na pewno moje podejście to faktycznie O(log n)? Właściwie robię to, co robisz w moim podejściu powyżej. Znalazłem mid za pomocą funkcji wyszukiwania binarnego i użyłem innej oddzielnej funkcji, aby znaleźć lewe elementy od środka i prawe elementy od środka dla dopasowań. Wyobraź sobie, że mam ogromne dane, powiedzmy 1000 danych, musiałbym iterować przez 1k z nich w lewo i prawo od środkowego lol. To jest równoważne O(N), prawda?
 – 
Cash-
19 listopad 2019, 18:18
A może O (Log N^2)?
 – 
Cash-
19 listopad 2019, 18:33
Mówisz, że moje podejście to O(log n) + O(N) ?? Jaka jest więc ostateczna wartość?
 – 
Cash-
19 listopad 2019, 18:36
@Cash: jeśli N jest rzędu n, algorytm staje się O(n), ponieważ wynik zawiera O(n) elementów. Jeśli N jest poniżej stałej, algorytm to O(log n).
 – 
MrSmith42
19 listopad 2019, 19:30
@Cash: jeśli nie jesteś pewien, czy Twoja implementacja ma oczekiwaną złożoność, musisz profilować jej wydajność dla różnych wartości n.
 – 
MrSmith42
19 listopad 2019, 19:31