2
\$\begingroup\$

I am trying to look for a substring in a list of strings. My end result is an array that contains the presence of substring first based on course.name and then based on course.description. Is there a better way to write the following code?

Firstly, I am looking for the substring in the course.name field using the indexOf method and adding it to the foundCourseList array.

let uniqueIds: string[] = [];
let foundCourseList: CourseItem[] = [];
this.props.courses.forEach((course: CourseItem) => {
    let courseNameListTobeSearchedIn = course.name.split(" ");
    
    courseNameListTobeSearchedIn.forEach((word: string) => {
        this.state.inputWord.split(" ").forEach((inputWord: string) => {
            if (word.toLowerCase().indexOf(inputWord.toLowerCase()) >= 0 && !uniqueIds.includes(course.id)) {
                foundCourseList.push(course);
                uniqueIds.push(course.id);
            };
        });
    });
});

Then I am looking for the same substring in the course.description field using the indexOf method and add it to the foundCourseList array. In that was the search results display results based on course.name followed by the results based on the course.description.

this.props.courses.forEach((course: CourseItem) => {
    let courseDescriptionTobeSearchedIn: string[];
    course.description && (courseDescriptionTobeSearchedIn = course.description.split(" "));
    
    if (courseDescriptionTobeSearchedIn) {
        courseDescriptionTobeSearchedIn.forEach((word: string) => {
            this.state.inputWord.split(" ").forEach((inputWord: string) => {
                if (word.toLowerCase().indexOf(inputWord.toLowerCase()) >= 0 && !uniqueIds.includes(course.id)) {
                    foundCourseList.push(course);
                    uniqueIds.push(course.id);
                };
            });
        });
    }
});
return foundCourseList;
\$\endgroup\$
4
\$\begingroup\$

There are several inefficient elements in the implementation.

Use a Set instead of an array for fast lookups

The code uses uniqueIds to keep track of the ids seen so far. The uniqueIds.includes does a linear scan over the items in the array. Using a Set would make that constant time.

Avoid repeated computations

There are several repeated computations here:

this.props.courses.forEach((course: CourseItem) => {
    let courseNameListTobeSearchedIn = course.name.split(" ");
    
    courseNameListTobeSearchedIn.forEach((word: string) => {
        this.state.inputWord.split(" ").forEach((inputWord: string) => {
            if (word.toLowerCase().indexOf(inputWord.toLowerCase()) >= 0 && !uniqueIds.includes(course.id)) {

For each course, for each word in the course name, this.state.inputWord is repeatedly split to words, and then lowercased. Assuming that this.state.inputWord doesn't change between iterations, it would be better to lowercase it and split it to words once, before this.props.courses.forEach begins.

For each input word, each word in the course name is repeatedly lowercased. It would be better to lowercase course.name once before splitting it to words.

The last kind of repeated computation is when there are duplicate words in the input or course names. If that's unrealistic, then it might not be worth to optimize. (Otherwise, you could use Set to remove duplicates.)

Putting it together

With the above ideas applied, the code becomes:

const uniqueIds: Set<string> = new Set();

const inputWords = this.state.inputWord
    .toLowerCase()
    .split(" ");

this.props.courses.forEach((course: CourseItem) => {
    course.name
        .toLowerCase()
        .split(" ")
        .forEach((word: string) => {
            inputWords.forEach((inputWord: string) => {
                if (!uniqueIds.has(course.id) && word.indexOf(inputWord) >= 0) {
                    foundCourseList.push(course);
                    uniqueIds.add(course.id);
                };
            });
        });
});

Notice that I switched the evaluation order in the conditions here:

if (!uniqueIds.has(course.id) && word.indexOf(inputWord) >= 0) {

The reason to order this way is because !uniqueIds.has(course.id) is the fast operation (thanks to making uniqueIds a Set), and word.indexOf(inputWord) is slower. This way, if the fast condition doesn't pass, the slower one can be skipped, so the ordering is significant.

Searching in both course.name and course.description

The same points I demonstrated above on the snippet searching in course.name apply equally to searching in course.description too.

Currently the search results based on course.name and the search results based on course.description both end up in the common array foundCourseList. As such it seems to make sense to combine the words from course.name and course.description into set to make sure you don't loop over the same word twice, and in this case a single loop over the combined keywords will suffice:

courses.forEach((course: CourseItem) => {
    const keywords: Set<string> = new Set();

    course.name
        .toLowerCase()
        .split(" ")
        .forEach(keywords.add, keywords);

    course.description
        .toLowerCase()
        .split(" ")
        .forEach(keywords.add, keywords);

    keywords
        .toLowerCase()
        .split(" ")
        .forEach((word: string) => {
            inputWords.forEach((inputWord: string) => {
                if (!uniqueIds.has(course.id) && word.indexOf(inputWord) >= 0) {
                    foundCourseList.push(course);
                    uniqueIds.add(course.id);
                };
            });
        });
});

Going even further

If the frequency of search operations is significantly higher than the frequency of changes to the underlying fields (name and description), then you may want to optimize further, to avoid recomputing the keywords over and over again to the same set of words.

For example you could add a keywords property and recompute it every time name or description changes, instead of recomputing it on every search. This optimization is not free, because it requires more memory to store the keywords, and more computation when name or description changes. It depends on your use case if this trade-off makes sense or not.

Finally, you could speed up the search even further by building a Trie from the keywords instead of a simple Set. This will cost even more memory, another trade-off.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for your answer. Its helpful to achieve a faster operation. However this did not address my problem where I am running the loop twice for searching for the input keyword in 2 arraylists: course.name and course.description. How can I run the loop just once to look for the input word in 2 arraylists course.name and course.description and add it to the foundCourseList array? \$\endgroup\$ Nov 7 '21 at 13:31
  • \$\begingroup\$ @user2140740 I added one more section now specifically for that point. (And then one more section with further improvement ideas.) \$\endgroup\$
    – janos
    Nov 7 '21 at 15:07
  • \$\begingroup\$ thanks for the improvement, however this code is missing sorting of the required results and I have just implemented it in the below solution \$\endgroup\$ Nov 8 '21 at 7:48
0
\$\begingroup\$

This is how I finally formulated the code such that it sorts the results firstly based on course.name and secondly based on course.description.

let foundCourseListName: CourseItem[] = [];
let foundCourseListDesc: CourseItem[] = [];
    const uniqueIds: Set<string> = new Set();   
    const inputWords = this.state.inputWord
                                 .toLowerCase()
                                 .split(" ");
   
    this.props.courses.forEach((course: CourseItem) => {
        course.name.toLowerCase().split(" ")
                   .forEach((word: string) => {
                      inputWords.forEach((inputWord: string) => {
                               if (!uniqueIds.has(course.id) && word.indexOf(inputWord) >= 0) {
                                   foundCourseListName.push(course);
                                   uniqueIds.add(course.id);
                               };
                       });
                   });
       if (course.description) {
          course.description.toLowerCase().split(" ")
                .forEach((word: string) => {
                    inputWords.forEach((inputWord: string) => {
                       if (!uniqueIds.has(course.id) && word.indexOf(inputWord) >= 0) {
                                       foundCourseListDesc.push(course);
                                       uniqueIds.add(course.id);
                                   };
                           });
                       });
                   }
               });
  return foundCourseListName.concat(foundCourseListDesc);

\$\endgroup\$
1
  • \$\begingroup\$ If you are looking for a review of additional code it is better to create a follow up question with a link back to the original question. \$\endgroup\$
    – pacmaninbw
    Nov 8 '21 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.