6
votes

façons d'accélérer le tri complet de comptage

J'ai rencontré une question sur Hackerrank. https://www.hackerrank.com/challenges/countingsort4

Ma première tentative a passé tout les cas de test sauf le dernier, en raison du délai d'attente. Après avoir échoué à proposer un algorithme plus efficace, j'ai amélioré le code en utilisant Stringbuilder au lieu de concaténer des chaînes directement. Cela a apporté la durée de fonctionnement de plus de 5 secondes à 3,5 secondes. P>

Ma question est-elle une autre manière que je peux améliorer la durée de fonctionnement? Merci. P>

Ce qui suit est mon code. P>

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        scanner.nextLine();

        int[] oriNum = new int[N];        
        String[] oriStr = new String[N];
        int[] count = new int[100];
        int[] indices = new int[100];
        int[] output = new int[N];

        // save the originals and the count array
        for (int i = 0; i < N; i++) {
            oriNum[i] = scanner.nextInt();
            oriStr[i] = scanner.nextLine().trim();
            count[oriNum[i]]++;
        }

        // accumulate the count array
        indices[0] = 0;
        for (int i = 1; i < 100; i++) {
            indices[i] = indices[i-1] + count[i-1];
        }

        // output order
        for (int i = 0; i < N; i++) {
            int num = oriNum[i];
            output[indices[num]++] = i;
        }

        int bar = N/2;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {            
            int index = output[i];
            if (index < bar) 
                sb.append("- ");
            else 
                sb.append(oriStr[index]+ " ");
        }
        System.out.println(sb.toString());
    }
}

java optimization string-concatenation counting-sort

3 commentaires

Au lieu de sb.append (oristr [index] + ""); utiliser sb.append (oristr [index]). Ajouter ("");

Cette question semble être hors tension car elle demande l'examen du code et en tant que telle appartient à la révision du code SE.

Si, par une chance que vous ayez atterri sur ce fil lors de la recherche sur la manière de compter le tri stable si nécessaire dans la question référée Hackerrank, veuillez consulter cet article - Comment compter bien trier un type stable?

3 Réponses :

7
votes

Vous devez essayer un lecteur en mémoire tampon simple au lieu de scanner. Scanner est étonnamment lent et j'ai participé à des compétitions de programmation où Scanner était la seule raison de "limite de temps dépassée".

2 commentaires

J'ai essayé la bufferedreader et la durée de fonctionnement a diminué de 3,5 secondes à 1,4 sec. Grande suggestion, merci!

Heh, vous êtes le bienvenu. J'ai été dans la même situation.

4
votes

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution 
{
    public static void main(String[] args)throws Exception 
{
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(in.readLine());
    int[] c=new int[100];
    String[][] dt=new String[100][10300];
    for(int i=0;i<n;i++)
    {
        String[] str=in.readLine().split(" ");
        int val=Integer.parseInt(str[0]);
        if(i<n/2)
            dt[val][c[val]]="-";
        else
             dt[val][c[val]]=str[1];
        c[val]++;
     }
  StringBuilder sb=new StringBuilder("");
    for(int i=0;i<100;i++)
       if(i<n)
        for(int k=0;k<c[i];k++)
            if(dt[i][k]!=null)
               sb.append(dt[i][k]+" ");
            else break;
    System.out.println(sb.toString());
 }
}

0 commentaires

0
votes

C'était mon approche du problème. (Il est en C ++).

void counting_sort(vector<int> &arr, int size,  vector<vector<string> > foo, vector<int> first_half)
{
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());

    int range = max - min + 1;

    int count[range] = {0};

    // counting frequency of numbers in array
    for (int i = 0; i < size; i++)
    {
        count[arr[i] - min]++;
    }

    // calculating cumulative sum
    for (int i = 1; i < range; i++)
    {
        count[i] += count[i - 1];
    }

    vector<vector<string> > output(size);

    // making the new sorted array
    for (int i = size - 1; i >= 0; i--) // traversing from backward for stability
    {
        output[count[arr[i]-min] - 1] = foo[i];
        count[arr[i]-min]--;
    }

    // copying the sorted array in original array
    int j=0;
    for (int i = 0; i < size; i++)
    {
        if(stoi(output[i][0]) == first_half[j])
        {
            cout << "- ";
            j++;
        }
        else
        {
            cout << output[i][1] << ' ';
        }
    }
}

// Complete the countSort function below.
void countSort(vector<vector<string>> arr) {

    vector<int> num;
    vector<int> first_half;
    for(int i=0; (unsigned)i<arr.size(); i++)
    {
        num.push_back(stoi(arr[i][0]));
        if(i < ((unsigned)arr.size()/2))
        {
            first_half.push_back(stoi(arr[i][0]));
        }
    }

    sort(first_half.begin(), first_half.end());
    counting_sort(num, num.size(), arr, first_half);
}

0 commentaires