Databases
StackOverflow2013
Postsdbo
POWhich data structure might be a more efficient implementation?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhich data structure might be a more efficient implementation?
    primarykey
    data
    text
    <p>I was doing an exercise on reading from a setup file in which every line specifies two words and a number. The number denotes the number of words in between the two words specified. Another file &ndash; <code>input.txt</code> &ndash; has a block of text, and the program attempts to count the number of occurrences in the input file which follows the constraints in each line in the setup file (i.e., two particular words <em>a</em> and <em>b</em> should be separated by <em>n</em> words, where <em>a</em>, <em>b</em> and <em>n</em> are specified in the setup file.</p> <p>So I've tried to do this as a shell script, but my implementation is probably highly inefficient. I used an array to store the words from the setup file, and then did a linear search on the text file to find out the words, and the works. Here's a bit of the code, if it helps:</p> <pre><code>#!/bin/sh j=0 count=0; m=0; flag=0; error=0; while read line; do line=($line); a[j]=${line[0]} b[j]=${line[1]} num=${line[2]} c[j]=`expr $num + 0` j=`expr $j + 1` done &lt;input2.txt while read line2; do line2=($line2) for (( i=0; $i&lt;=50; i++ )); do for (( m=0; $m&lt;j; m++)); do g=`expr $i + ${c[m]}` g=`expr $g + 1` if [ "${line2[i]}" == "${a[m]}" ] ; then for (( k=$i; $k&lt;$g; k++)); do if [[ "${line2[k]}" == *.* ]]; then flag=1 break fi done if [ "${b[m]}" == "${line2[g]}" ] ; then if [ "$flag" == 1 ] ; then error=`expr $error + 1` fi count=`expr $count + 1` fi flag=0 fi if [ "${line2[i]}" == "${b[m]}" ] ; then for (( k=$i; $k&lt;$g; k++)); do if [[ "${line2[k]}" == *.* ]]; then flag=1 break fi done if [ "${a[m]}" == "${line2[g]}" ] ; then if [ "$flag" == 1 ] ; then error=`expr $error + 1` fi count=`expr $count + 1` fi flag=0 fi done done done &lt;input.txt count=`expr $count - $error` echo "| Count = $count |" </code></pre> <p>As you can see, this takes a lot of time.</p> <p>I was thinking of a more efficient way to implement this, in C or C++, this time. What could be a possible alternative implementation of this, efficiency considered? I thought of hash tables, but could there be a better way? </p> <p>I'd like to hear what everyone has to say on this.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USgniourf_gniourf
    1. USCaife
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhich data structure might be a more efficient implementation?
      1. USCaife
      1. VTFavorite
    2. VO
      singulars
      1. POWhich data structure might be a more efficient implementation?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhich data structure might be a more efficient implementation?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COCan you post some input file samples ?
      singulars
      1. POWhich data structure might be a more efficient implementation?
      1. USMatthieu Rouget
    2. COOk. Suppose the input file contains the sentence "Iterators are the mechanism that makes it possible to decouple algorithms from containers." The setup file contains a single line, "mechanism possible 3". The program would then return 1 since there's one occurrence of such a condition.
      singulars
      1. POWhich data structure might be a more efficient implementation?
      1. USCaife
    3. COAre the pairs ordered? I.e. should "possible mechanism 3" also yield a match?
      singulars
      1. POWhich data structure might be a more efficient implementation?
      1. UStripleee
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload